# What is Recursion?

This lesson explains the basics of recursion.

We'll cover the following

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

$2^3=8$

### Code

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

#include<iostream>using namespace std;//recursive functionint power(int x, int n) {  if (n == 1) { //base case    return x;  } else {    return x * power(x, n - 1);//recursive case  }}//driver functionint 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: