The Nature of RecursionComparison of Iteration and RecursionRecursion - I1RECURSIONRecursion is a powerful problem-solving strategy. Solves large problems by reducing them tosmaller problems of the same form. The subproblems have the same form as the originalproblem.To illustrate the basic idea, imagine you have been appointed as funding coordinator for a largecharitable organization. Your job is to raise one million dollars in contributions to meet theexpenses of the organization. If somebody can write out a check for the entire amount, your jobis easy. On the other hand, it may not be easy to locate persons who would be willing to donateone million dollars. However people don’t mind donating smaller amounts. If lets say $100 is a good enoughamount, than all you have to do is to call 10,000 friends to complete the task. Well, it is goingto be a tall order for you, but you know that your organization has a reasonable supply ofvolunteers across the country.You may start off by finding 10 dedicated supporters in different parts of the country andappoint them regional coordinators. So each person now has to raise $100,000. It is simplerthan 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 eachwithin their region and asking each to raise $10,000. The delegation process can continue untilthere are volunteers who have to go around raising donations of $100 each from individualdonors.The following structure is a psuedocode for the problem: Ask funding coordinator to collectfund void collect (int fund){if ( fund <=100) {contact individual donor.} else {find 10 volunteers.Get each volunteer to collect fund/10 dollarsPool the money raised by the volunteers. }}2Notice that the basic nature of the problem remains the same, i.e. collect n dollars, where valueof n is smaller each time it is called. To solve the problem you can invoke the same functionagain.Having a function to call itself is the key idea of recursion in the context of programming. Astructure 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 analternative to iterative problem solving strategy.Example : Let us consider the Factorial Functionn! = n * (n-1) * (n-2) * … * 2 * 10! = 1Iterative 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 mathematicalproperty of factorials. Each factorial is related to factorial of the next smaller integer :n! = n * (n-1)!3To make sure the process stops at some point, we define 0! to be 1. Thus the conventionalmathematical definition looks like this: n! = 1 if n = 0n! = n*(n-1)! if n > 0This 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));}4The Nature of Recursion1) 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 arecloser to stopping cases.3) Eventually the problem can be reduced to stopping cases only, which are relatively easyto solve.In general:if (stopping case)solve itelse reduce the problem using recursionTracing a Recursive FunctionLet us try to follow the logic the computer uses to evaluate any function call. It uses a stack tokeep track of function calls. Whenever a new function is called, all its parameters and localvariables 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 statement f= factorial (4);when main calls factorial, computer creates a new stack frame and copies the argument valueinto the formal parameter n. main fact1if (n ==0) return (1);else return (n * fact(n-1)); n = 45To evaluate function fact1, it reaches the point where it needs the value of fact (n-1) to bemultiplied by n This initiates a recursive call. At this stage picture is like thismain fact1 n=4if (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 shownbelowmain fact1 fact2if (n ==0) return (1);else return (n * fact(n-1)); n= 3and 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 = 0Now the situation changes. 6Because 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 fact4if (n ==0) return (1);else return (n * factorial(n-1)); value 1 n = 1Now 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 fact3if (n ==0) return (1);else return (n * factorial(n-1)); value 1 n =2Because n is 2, a 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 = 3Now the value returned is 3 x 2 to previous level as shown:7Main fact1 if (n ==0) return (1);else return (n * factorial(n-1)); value 6 n = 4Finally the value 4 x 6 is calculated at 24 is returned to the main program.Exponentiation:Raising an integer to a power (which is also an integer) involves successive multiplication by the base. However, as the result becomes quite large very soon, it would work only if there is a machine to hold large integers. xn requires n-1 multiplications.power( x, n){ if ( n==0) return 1; if(n==1) return x; else return ( x * power( x , n – 1 )