The Nature of RecursionMain fact1 fact2 fact3 fact4 fact5Example 6: Fibonacci SequenceComparison of Iteration and RecursionIterative FibonacciCoding the solutionRECURSIONRecursion is a powerful problem-solving strategy. Solves large problems by reducing them to smallerproblems of the same form. The subproblems have the same form as the originalproblem.To illustrate the basic idea,Funding coordinator for a large charitable organization. Job: to raise one million dollars in contributions to meetthe expenses of the organization. not easy to locate persons who would be willing todonate one million dollars. However people don’t mind donating smaller amounts. lets say $100 is a good enough amount call 10,000 friends to complete the task. organization has a reasonable supply of volunteers acrossthe country.1find 10 dedicated supporters in different parts of thecountry and appoint them regional coordinators.So each person now has to raise $100,000. It is simpler than raising one million, but hardlyqualifies to be easy. They can adopt the same strategy, i.e. delegate parts of the job to another 10 volunteerseach within their region and asking each to raise $10,000. The delegation process can continue until there arevolunteers who have to go around raising donations of$100 each from individual donors.2The following structure is a psuedocode for theproblem:======================================== 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 dollarsPool the money raised by the volunteers. }}Basic nature of the problem remains the same, i.e. collect n dollars, value of n is smaller each time it is called. To solve the problem invoke the same function again.3Having a function to call itself is the key idea ofrecursion in the context of programming. A structure providing a template for writing recursivefunctions is as follows: If (test for a simple case) {Compute simple solution without recursion } else {break the problem into similar subproblems solve subproblem by calling this function recursively.Reassemble the solution to the subproblems Recursion is an example of divide-and-conquerproblem solving strategy. It can be used as an alternative to iterative problemsolving strategy.4Example 1: space shuttle taking offvoid count_down(int n){if (n <= 0)printf(“\nBlast off.\n”); else{printf(“%d! “, n);count_down(n-1); }}int main (){count_down(10);}5Example 2: 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 );}6Recursive definition:In the recursive implementation there is no loop. We make use of an important mathematical property offactorials. Each factorial is related to factorial of the next smallerinteger :n! = n * (n-1)!To make sure the process stops at some point, we define0! to be 1. conventional mathematical definition : 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 i.e. find factorial ofn – 1 7In C:int fact(int n){if (n ==0) return (1);else return (n * fact(n-1));}The Nature of Recursion1) One or more simple cases of the problem (called thestopping cases) have a simple non-recursive solution.2) The other cases of the problem can be reduced(using recursion) to problems that are closer tostopping cases.3) Eventually the problem can be reduced to stoppingcases only, which are relatively easy to solve.In general:8if (stopping case)solve itelse reduce the problem using recursionTracing a Recursive FunctionLet us try to follow the logic the computer uses toevaluate any function call. It uses a stack to keep track of function calls. Whenever a “new” function is called, all its parameters and local variablesalong with the memory address of the calling statement are pushed onto system stack(this gives the computer the return point after executionof the function) In the factorial example , suppose “main” has astatement 9f= factorial (4);when main calls factorial, computer creates a new stack frame and copies the argument value into the formal parameter n.main fact1if (n ==0) return (1);else return (n * fact(n-1)); n = 4To evaluate function fact1, it reaches the point where itneeds the value of fact (n-1) to be multiplied by n This initiates a recursive call. At this stage picture is like thismain fact1 n=410if (n ==0) return (1);else return (n *fact(n-1)); ? current value of n is 4, n-1 takes the value 3, and another fact call is invokedmain fact1 fact2if (n ==0) return (1);else return (n * fact(n-1)); n= 3and the process continues till fact is called 5 times and ngets the value 0:Main fact1 fact2 fact3 fact4 fact5 if (n ==0) return (1);11else return (n * factorial(n-1)); n = 0Because 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 = 112Now 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 = 313Now the value returned is 3 x 2 to previous level as shown:Main 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.14Example: Palindrome A Palindrome is a string of characters that reads the same backwards and forwards (e.g. noon, level, deed, mom). Palindromes can be defined recursively. Any