The Nature of RecursionRecursion - IRecursion is a powerful problem-solving strategy. Solves large problems by reducing them to smaller problems of the same form. The subproblems have the same form as the original problem. To illustrate the basic idea, imagine you have been appointed as funding coordinator for a large charitable organization. Your job is to raise one million dollars in contributions to meet the expenses of the organization. If somebody can write out a check for the entire amount, your job is easy. On the other hand, it may not be easy to locate persons who would be willing to donate one million dollars. However people don’t mind donating smaller amounts. If lets say $100 is a good enough amount, than all you have to do is to call 10,000 friends to complete the task. Well, it is going to be a tall order for you, but you know that your organization has a reasonable supply of volunteers across the country. You may start off by finding 10 dedicated supporters in different parts of the country and appoint them regional coordinators. So each person now has to raise $100,000. It is simpler than raising one million, but hardly qualifies to be easy. Maybe they can adopt the same strategy, i.e. delegate parts of the job to 10 volunteers each within their region and asking each to raise $10,000. The delegation process can continue until there are volunteers who have to go around raising donations of $100 each from individual donors. The following structure is a psuedocode for the problem: Ask funding coordinator to collect fund void collect (int fund) { if ( fund <=100) { contact individual donor. } else { find 10 volunteers. Get each volunteer to collect fund/10 dollars Pool the money raised by the volunteers. } } Notice that the basic nature of the problem remains the same, i.e. collect n dollars, where value of n is smaller each time it is called. To solve the problem you can invoke the same function again. Having a function to call itself is the key idea of recursion in the context of programming. A structure providing a template for writing recursive functions is as follows:If (test for a simple case) { Compute simple solution without recursion } else { break the problem into similar subproblems solve these by calling function recursively. Reassemble the solution to the subproblems Recursion is an example of divide-and-conquer problem solving strategy. It can be used as an alternative to iterative problem solving strategy. Example of a recursive function: Compute factorial of a number Example : Let us consider the Factorial Function n! = n * (n-1) * (n-2) * … * 2 * 1 0! = 1 Iterative solution: int fact(int n) { int p, j; p = 1; for ( j=n; j>=1; j--) p = p* j; return ( p ); } Recursive definition: In the recursive implementation there is no loop. We make use of an important mathematical property of factorials. Each factorial is related to factorial of the next smaller integer :n! = n * (n-1)! To make sure the process stops at some point, we define 0! to be 1. Thus the conventional mathematical definition looks like this: n! = 1 if n = 0 n! = n*(n-1)! if n > 0 This definition is recursive, because it defines the factorial of n in terms of factorial of n – 1. The new problem has the same form, which is, now find factorial of n – 1 . In C: int fact(int n) { if (n ==0) return (1); else return (n * fact(n-1)); } The Nature of Recursion 1) One or more simple cases of the problem (called the stopping cases) have a simple non-recursive solution. 2) The other cases of the problem can be reduced (using recursion) to problems that are closer to stopping cases. 3) Eventually the problem can be reduced to stopping cases only, which are relatively easy to solve. In general: if (stopping case) solve it else reduce the problem using recursion Tracing a Recursive Function Let us try to follow the logic the computer uses to evaluate any function call. It uses a stack to keep track of function calls. Whenever a new function is called, all its parameters and local variables are pushed onto the stack along with the memory address of the calling statement (this gives the computer the return point after execution of the function) In the factorial example , suppose “main” has a statementf= factorial (4); when main calls factorial, computer creates a new stack frame and copies the argument value into the formal parameter n. main fact1 if (n ==0) return (1); else return (n * fact(n-1)); n = 4 To evaluate function fact1, it reaches the point where it needs the value of fact (n-1) to be multiplied by n This initiates a recursive call. At this stage picture is like this main fact1 n=4 if (n ==0) return (1); else return (n *fact(n-1)); ? As current value of n is 4, n-1 takes the value 3, and another fact call is invoked, as shown below main fact1 fact2 if (n ==0) return (1); else return (n * fact(n-1)); n= 3 and the process continues till fact is called 5 times and n gets the value 0:Main fact1 fact2 fact3 fact4 fact5 if (n ==0) return (1); else return (n * factorial(n-1)); n = 0 Now the situation changes. Because n is 0, the function parameter can return its result by executing the statement return(1); The value 1 is returned to the calling frame, which now becomes the top of stack as shown: Main fact1 fact2 fact3 fact4 if (n ==0) return (1); else return (n * factorial(n-1)); value 1 n = 1 Now the computation proceeds back through each of recursive calls. In above frame n=1 so it returns the value 1 to its caller , now the top frame shown here: Main fact1 fact2 fact3 if (n ==0) return (1); else return (n * factorial(n-1)); value 1 n =2Because n is 2, the value 2 is passed back to previous level: Main fact1 fact2 if (n ==0) return (1); else return (n * factorial(n-1)); value 2 n = 3 Now the value returned equals 3 x 2 to previous level as shown: Main fact1 if (n ==0) return (1); else return (n * factorial(n-1)); value 6 n = 4 Finally the value 4 x 6 ( = 24) is returned to the main program. We can summarize the steps involved in tracing this function for n= 4 int fact(int n) { if (n ==0) return (1);