Have you ever
had a dream that you were dreaming? Have you ever stood in a room with many
reflecting mirrors, or have you ever viewed a landscape and in the distance the
image begins to fade? Have you
recalled memories back to your childhood? Have you opened a dictionary to the
middle, and then to the middle of the middle to look for a word such as
“heuristic”? All these actions have something in common.
Somehow, each action is recurring (calling) itself. There are many
problems of this type that can be solved by reiterating or including the problem
as part of the solution. A problem is recursive when its solution requires
continually recalling the original problem. Eventually the problem is broken
down to the point where a direct solution can be reached. Recursive solutions
are elegant and natural because the whole problem can usually be expressed in
two statements. A statement that has a direct solution (base solution) is not
recursive. While a statement that calls itself and, with each call, simplifies
the problem to the point that the base solution is reached is recursive.
If you are
confused as to what recursion is, it will soon become clear. There are many
recursive patterns in nature, such as a rabbit breeding or the growing branches
of a tree. Grasping the concept of recursion may require detailed knowledge.
Some simple mathematical examples such as Factorial (n!) or Fibonacci number
series can express the concept of recursion clearly.
Let us look
at a recursive problem and try to formulate it in a logical way, so that you can
better understand recursion. Ask yourself this question: “Who are your
ancestors?”
“My parents
are my ancestors” is one answer, but this does not satisfy the question. Your
second answer is “My parent’s ancestors are my ancestors”. You can see
that the solution is recursive because the word ancestor (which is the problem)
is used to define the solution. Together,
the two statements (shown below) cover all ancestors. However, when it comes to
a specific problem in a given database, such as
“Ancestorof (x,Mary)?” the answer will eventually end with a
non-recursive statement (base solution).
ancestorof(x,y)
if parentof(x,y)
ancestorof(x,y) if parentof(x,z)
and ancestorof(z,y)
Now look at
the following recursion as to who is your boss?
bossof(x,y) if supervises(x,y)