RecursionDefinition: Any time the body of a function contains a call tothe function itself.So, just as you are allowed to call function B from withinfunction A, you are ALSO allowed to call function A fromwithin function A!Potential Problem: But if my function calls itself, how can weever finish executing the original function?What this means is that some calls to the function MUST NOTresult in a recursive call. I think this can best be seen from anexample.// Pre-conditions: e is greater than or equal to 0.// Post-conditions: returns be.int Power(int base, int exponent) { if ( exponent == 0 ) return 1; else return (base*Power(base, exponent-1));}To convince you that this works, let’s look at an example:Say we were trying to evaluate the expressionPower(5, 2) Power(5,2) returns 5*Power(5,2-1) = 5*Power(5,1)To evaluate this expression we must evaluate:Power(5,1) returns 5*Power(5, 0)Finally, we have:Power(5,0) returns 1.Thus, Power(5,1) returns 5*1, which is 5.Finally, Power(5,2) returns 5*Power(5,2-1) = 5*5 = 25,and we are done.General Structure of Recursive FunctionsWhat we can determine from the example above is that ingeneral, when we have a problem, we want to break it downinto chunks, where one of the chunks is a smaller version of thesame problem.(In the case of Power, we utilized the fact that xy = x * xy-1, andrealized that xy-1 is in essence an easier version of the originalproblem.)Eventually, this means that we break down our originalproblem enough that our sub-problem is quite easy to solve. Atthis point, rather than making another recursive call, directlyreturn the answer, or complete the task at hand.So, ideally, a general structure of a recursive function has acouple options: 1) Break down the problem further, into a smaller subproblem2) OR, the problem is small enough on its own, solve it.When we have two options, we often use an if statement. This istypically what is done with recursion. Here are the two generalconstructs of recursive functions:Construct 1if (terminating condition) {DO FINAL ACTION}else {Take one step closer to terminating conditionCall function RECURSIVELY on smaller subproblem}Construct 2if (!(terminating condition) ) {Take a step closer to terminating conditionCall function RECURSIVELY on smaller subproblem}Typically, functions that return values take on the first construct, while void recursive functions use the second construct. Note that these are not the ONLY layouts of recursive programs, just common ones.Example using construct 1Let’s write a function that takes in one positive integerparameter n, and returns the sum 1+2+...+n. (You probably didthis is C numerous times, yet surprisingly it never gets old!)Step 1: We need to solve this problem is such a way that part ofthe solution is a sub-problem of the exact same nature.Let f(n) denote the value 1+2+3+...+nUsing our usual iterative logic, we havef(n) = 1 + (2 + 3 + ... + n)But, 2+3+... + n IS NOT a sub-problem of the form 1+2+...+n.But, let’s try this:f(n) = 1 + 2 + ... + n = n + (1 + 2 + ... + (n-1)) So, here we have gotten the expression 1 + 2 + ... + (n-1) whichIS a sub-problem we were looking for. Hence, we have f(n) = 1 + 2 + ... + n = n + (1 + 2 + ... + (n-1)) = n + f(n-1)If we look at the construct 1, the first thing we need todetermine is a terminating condition. We know that f(0) = 0, soour terminating condition can be n=0.Furthermore, our recursive call needs to be returning anexpression for f(n) in terms of f(k), for some k<n. In this case,we just found that f(n) = n + f(n-1). So, now we can write ourfunction:// Pre-condition: n is a positive integer.// Post-condition: Function returns the sum 1+2+...+nint Triangle_Number(int n) { if ( n == 0 ) return 0; else return (n + Triangle_Number(n-1));}Let’s compare this to the ITERATIVE version you would havewritten in COP3223:// Pre-condition: n is a positive integer.// Post-condition: Function returns the sum 1+2+...+nint Triangle_Number(int n) {int index, sum = 0;for (index=1; index <=n; index++)sum = sum + index;return sum;}Example using construct 2We must write a function for an example of construct 2. Acouple lectures ago, when I introduced loops, we wrote analgorithm that printed out a tip chart. We could have just aseasily made that a function that takes in the lowest dollar valueand highest dollar value on the chart. The method header ofthe function would look like:// The function prints out a chart with the appropriate tips// for meals ranging from first_val to last_val number of // dollars, for every whole dollar amount. Both parameters// must be positive integers.void Tip_Chart (int first_val, int last_val)Now, let’s consider writing this function recursively.First, we need to determine a terminating condition. Thatseems to be relatively simple: if the lowest dollar amount isgreater than the highest dollar amount, then the chart is emptyand we are done.Next, we need to figure out how to break down our task intotwo steps: one that does part of the job, and secondly arecursive step.1) It is clear that the first value we have to print of the chart isassociated with the lowest dollar value, since that mustappear on the chart first. Printing out this line of the tipchart can be the part of the job we accomplish.2) Now, are we left with a sub-problem of the same nature?Yes! We simply now need to print a tip chart from the lowestdollar value+1 to the highest dollar value.So, now, we can use these steps to come up with the function:#define TIP_RATE 0.15// Pre-condition: Both parameters are integers with the first// one being less than or equal to the second one.// Post-condition: A tip chart will be printed out, with a row for// each dollar amount ranging in between the// value of the two parameters.void Tip_Chart (int first_val, int last_val)if ( !(first_val > last_val) ) {printf(“On a meal of $%d”, first_val);printf(“ you should tip $%lf\n”, first_val*TIP_RATE);Tip_Chart(first_val + 1, last_val)}}Using a Stack to Trace Recursive CodeA stack is a construct that can be used to store and retrieveitems. It works just like a stack of plates in the cafeteria: Thelast plate placed on the top is the first one that must beremoved.