Recursion is when a function calls itself again and again until it reaches a specified stopping condition.

Parts of a Recursive Function

Each recursive function has two parts:

  • Base Case: The base case is where the call to the function stops i.e., it does not make any subsequent recursive calls

  • Recursive Case: The recursive case is where the function calls itself again and again until it reaches the base case.

How do you solve a problem using recursion?

To solve a problem using recursion, break the problem into one or more smaller problems, and add one or more base conditions that stop the recursion. i.e. make a recurrence relation for that problem.

How is memory allocated to different function calls in recursion?

When a function is called, the state of that function is saved in a stack. Each recursive call pushes a new stack frame. When the base case is reached the stack frames start popping from the stack until the stack becomes empty.

Example

The task is to calculate x power n:

For example,

if x=2 and n=3

23=82^3=8

Code

The following code explains how to calculate x power n using recursion:

#include<iostream>
using namespace std;
//recursive function
int power(int x, int n) {
  if (n == 1) { //base case
    return x;
  } else {
    return x * power(x, n - 1);//recursive case
  }
}
//driver function
int main()
{
  int x=2;
  int n=3;
 cout<<x<<" ^ "<<n<<" : ";
 cout<<power(2, 3);
}

Visualization Through the Stack

The following illustration helps to visualize the code through a stack: