What is Recursion?
This lesson explains the basics of recursion.
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
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 casereturn 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: