### Creating a power function using Recursion

Below is an example of how to calculate the x to the power of n. This tutorial expects you to understand the following:

Example:

1 2 | pow(2,3); pow(5,4); |

Result:

1 2 | 8 625 |

### Iterative version of a function that calculates the power function

To understand how to calculate the power function using recursion, let’s write a simple algorithm that will do it for us using iteration.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | int power(int base, int exp) { if ( exp == 0 ) { return 1; } //Initial value for the result is the base int result = base; //Multiplies the base by itself exp number of times for ( int i = 1; i < exp; i++ ) { result = result * base; } return result; } |

### Calculating the power function using recursion

So how would we go by solving this using recursion? First of all we need a function header.

1 | int power(int base, int exp) |

Next, what would be our base case? When we are trying to calculate n to the power of 0, the result should be 1. Also, when we try calculating n to the power of 1, the result should be n.

1 2 3 4 5 6 | int power(int base, int exp) { //Return 1 when n is 0 if ( n == 0 ) return 1; else if ( n == 1 ) return base; } |

Now, how would we go on by computing the power function using recursion? Let’s come up with a formula by calculating the following.

1 2 3 4 5 6 7 8 9 10 11 12 13 | power(2,0) = 1; power(2,1) = 2; power(2,2) = 2 * power(2,1) = 2 * 2 = 4; power(2,3) = 2 * power(2,2) = 2 * 4 = 8; power(2,4) = 2 * power(2,3) 2 * 8 = 16; ... power(base, exp) = base * power(base, exp-1); |

Translating the above formula to code, is then fairly trivial. This would allow us to apply our power function to any two positive integers.

1 2 3 4 5 6 7 8 9 10 11 12 | int power(int base, int exp) { //Return 1 when n is 0 if ( exp == 0 ) return 1; else if ( exp == 1 ) return base; else return base * power(base, exp-1); int result = base; } |

Have any questions? Feel free to ask below or request any other examples.

### Going further

- 1. How would you make this function take care of negative exponents?