CHAPTER 10
RECURSION: FUNCTION CALLING ITSELF
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.
WORD EXAMPLES OF RECURSION:
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)
bossof(x,y) if supervises(x,z) and bossof(z,y)
In the above example, which statement is not recursive and which is it? Keep in mind that in order to solve the problem we need both of the above statements.
MATHEMATICAL EXAMPLES OF RECURSION
The two common examples of recursion are: Factorial (n!) and Fibonacci number series. A Factorial of a number is defined by the multiplication of that number with the Factorial of its previous number. However, the factorial of zero is defined as 1.
A Fibonacci of a number is the sum of the Fibonacci of the two previous numbers (one before and two before). However, the first Fibonacci is 1 and the second Fibonacci is 1.
factorial(n) is n * factorial(n-1) if n>0
if n is 0 factorial is 1;
What is the factorial of 4 – factorial(4)?
4! is 4* 3!
where 3! is 3 * 2!
where 2! is 2*1!
where 1! is 1 * 0!
where 0! is 1 (hint: no more recursion)
Now that we found the 0!, we can ladder up and compute 1*1*2*3*4 which is 24. The above structure is known as a “tree structure”.
A RECURSIVE PROGRAM
We know that the main program can call another function to perform a task. However, a function is recursive when the function calls itself either directly or indirectly through another function. In a recursive algorithm, the solution expressed in terms of itself (a smaller version) is known as the general case. The non-recursive exception case is known as the base case. The following programs illustrate a non-recursive and a recursive version of a “space shuttle countdown” program. The intention of the below program is to show a recursive program and not to compare it with its' non-recursive version.
RECURSION AND PASS OF PARAMETERS
Pass of parameters (arguments) to a function plays a major role in recursion. In order to reach the condition to exit the recursion (base case), a value of parameter (new value) is substituted for the old value. In Figure 10.1 , line 4, in the recursive function call the value of n-1 will substitute for n in the function countdown(int n).
1. #include<iostream>
2. using namespace std;
3. countdown(int n){
4. if (n>0){ cout<<n<<endl;
5. countdown(n-1); }//IF
6. else cout <<"BLAST OFF "<<endl;
7. return 0; }//COUNTDOWN
8. main() {
9. int count=9;
10. cout<<"START COUNTING:"<<endl;
11. countdown(count);
12. return 0; }//MAIN
1. #include<iostream>
2. using namespace std;
3. countdown(int n){
4. while (n>0) { cout<<n<<endl;
5. n=n-1; }//WHILE
6. cout <<"BLAST OFF "<<endl;
7. return 0; }//COUNTDOWN
8. main(){
9. int count=9;
10. cout<<"START COUNTING:"<<endl;
11. countdown(count);
12. return 0; }//MAIN
A FACTORIAL PROGRAM
The following two programs illustrate a recursive and a non-recursive version of a factorial number. While the non-recursive version is faster, it doesn’t preserve the recursive nature of factorial problems.
1. #include<iostream>
2. using namespace std;
3. factorial(int); //function prototype
4. main(){
5. int n=4;
6. cout<<" FACTORIAL OF "<<n<<" IS "<<factorial(n)<<endl;
7. return 0; }//MAIN
8. factorial(int n){
9. if (n>0) return n* factorial(n-1);
10. else return 1;
11. }//FACTORIAL
1. #include<iostream>
2. using namespace std;
3. factorial (int n){
4. int f=1;
5. while(n>0){ f=f*n;
6. n=n-1; }//WHILE
7. return f; }//FACTORIAL
8. main(){
9. int n=4;
10. cout<<" FACTORIAL OF "<<n<<" IS "<<factorial(n)<<endl;
11. return 0;
12. }//MAIN
RECURSION VERSUS ITERATION
A repetitive problem can be solved recursively or iteratively. Depending on the problem itself, its complexity, restrictions on the amount of execution time or the available memory, one may be more suitable for solving the problem. While a recursive program may be slower and use more memory than its iterative version, recursive problems by their nature offer a direct, simple and elegant solution to problems that would be cumbersome if a recursive solution were not used.
RECURSION IN PROGRAMMING LANGUAGES
C/C++ like most of today’s programming languages supports recursion. Several early languages such as FORTRAN, COBOL and BASIC do not use recursion. Languages such as LISP and PROLOG use recursion extensively and structure data in such a way that makes recursion a beautiful tool to have. To improve performance in some dialects of LISP, the compiler converts the recursive program written by the user to an iterative program before execution.
WHY RECURSION?
Keep in mind that not all problems are recursive by nature and they do not offer easy recursive solutions. For those that do, it is better to be solved recursively rather than by iteration (loop). The recursive solution is elegant, short, and preserves the nature of the problem (one-to-one map). Moreover, when you have a recursive solution to a problem (by some thinking), it is not easy to forget. When writing a recursive program just map the solution one-to-one, have confidence that things will work right.
A PROBLEM WITH RECURSION: INFINITE REPETITION
Every function uses memory to track its local variables, parameters, and return addresses. When a function calls itself, each function call has a separate memory location assigned to it. For example, if a function is called five times, there are five different return addresses set aside. A recursive function must come to an end; otherwise the program will use all the available memory and will crash.