Recursion Lab Part 1

Recursion is the process in which a procedure calls itself – makes a clone of itself.  One of the benefits of using recursion is that it makes algorithms more compact and simple.  The characteristics of recursion are, as stated before, the procedure or function calls itself, there must be some terminating condition (ALWAYS ensure that your recursive procedure has a terminating condition), and the procedure must move closer to the terminating condition.

Skeletons for recursive procedures:

if (terminating condition) then   do final actions else   move one step closer to terminating condition   call "clone" of procedure endif

if (NOT (terminating condition)) then   move one step closer to terminating condition   call "clone" of procedure endif

The first skeleton checks to see if the terminating condition is met, if it is, the final actions are done; however, if the terminating condition is not met, the procedure moves one step closer to the terminating condition and calls a clone of itself. The second skeleton checks to see if the terminating condition is not met, and if it is not, the procedure moves one step closer to the terminating condition and calls a clone of itself.

Now that you know the basic skeletons for recursion, lets move on to writing the first application. Create an application that will take in a number and raise it to some power which is determined by the user. Now before we begin coding we need to stop and think about how we are going to write this program recursively. First you need to ask yourself what is going on when we raise a number by a power. An example of the type of calculations that you are performing (supposing you choose 4 as your base and 4 as the power to raise the number to). Using this line of thinking the module should perform calculation similar to these: (4)(4)(4)(4). Now that you know how to perform the calculation, it is time to write the application.
 
Prompt the user for the base and the power at which to raise it. Pass that information to the procedure which will handle the calculation. It is in this procedure that you will be using recursion to do the calculation. Remember, in recursion, you have to make a clone of the function inside of the function, which should look similar to this:

num * multi(power-1, num);

Remember, in recursion, there has to be a terminating condition to work towards, for this example, the terminating condition is when power = 0. We work closer to the terminating condition by subtracting one from power. To do this, your code should look similar to the following:

if (power != 0) {       ans = num * multi(power-1, num); } else {       return 1; }

Let’s put all of this code together and code the procedure, multi. Your code should look similar to this:

#include <iostream> using namespace std; int multi (int power,int num); void main () {       int numToRaise = 0;       int toPower = 0;       int answer = 0;       cout<<"Enter number to increase by power: ";       cin>>numToRaise;       cout<<"Enter power to raise that number to: ";       cin>>toPower;       answer = multi (toPower, numToRaise);       cout<<answer<<endl; } int multi (int power, int num) {       int ans = num;       if (power != 0)       {             ans = num * multi(power-1, num);       }       else       {             return 1;       }       return ans; }

Compile and run your code – your output should be similar to this: