Recursion means “solving a problem using the solution of smaller subproblems (smaller version of the same problem)” or “defining a problem in terms of itself”. This is a widely used idea in data structures and algorithms to solve complex problems by breaking them down into simpler ones. In this blog, we will understand the basic concepts of recursion and help you refine one of the critical problem-solving skills in data structures and algorithms.
Recursion comes up in mathematics frequently, where we can find many examples of expressions written in terms of themselves. For example, calculating the value of nth factorial and nth Fibonacci numbers is one of the best examples. But recursion is just as much a programming concept!
Suppose you are standing in a long queue of people. How many people are directly behind you in the line?
Once a person receives a response, they add 1 for the person behind them and respond to the person that asked them or the person standing in front of them.
int peopleCount(Person currPerson)
{
if (noOneBehind(currPerson))
return 0
else
{
Person personBehind = currPerson.getBehind()
return peopleCount(personBehind) + 1
}
}
In programming terms, recursion is a function calling itself until a “base condition” is true to produce the correct output.
void function(input size)
{
base case
.. .. ...
function(smaller input size) //recursive call
.. .. ...
}
int main()
{
... .. ...
function(input size)
... .. ...
}
In other words: To solve a problem, we solve a problem that is a smaller instance of the same problem, and then use the solution to that smaller instance to solve the original problem. For a recursive algorithm to work, smaller subproblems must eventually arrive at the base case.
In simple words, any recursive algorithm has two parts: base case and recursive structure.
Base case is a terminating condition where a function immediately return the result. This is the smallest version of the problem for which we already know the solution.
Recursive structure is an idea to design a solution of a problem via the solution of its smaller sub-problems i.e. same problem but for a smaller input size. We continue calling the same problem for smaller input sizes until we reach the base case of recursion.
sum(x, y)
= x, if(y == 0)
= 1 + sum (x, y - 1), if(y > 0)
product(x, y)
= 0, if(y == 0)
= sum (x, product(x, y - 1), if(y > 0)
power(x, y)
= 1, if(y == 0)
= product (x, power(x, y - 1), if(y > 0)
The factorial of a non-negative integer is a multiplication of all integers smaller than or equal to n. For example. the factorial of 5 is 1 * 2 * 3 * 4 * 5 = 120
According to the mathematical definition of the factorial of n, we can write:
n!
= n * (n - 1) * (n - 2) *….* 2 * 1
= n * (n - 1)!
=> nth factorial = n * (n - 1)th factorial
If we calculate the value of the (n - 1)th factorial, we can easily calculate the value of the nth factorial. It means we can solve the problem of input size n with its smaller problem of the input size (n - 1). In other words, we can solve this problem by using the idea of recursion!
Suppose the function fact(n) and fact(n - 1) return the value of the nth and (n - 1)th factorial, respectively, then we can write the following recursive structure:
fact(n) = n * fact(n - 1)
In every recursive solution, there must be a terminating condition or base case where our recursion will directly give us results without breaking it again into the sub-problem. If we observe the above recursive structure, then we find the following chain of recursive calls behind the scene:
fact(n)
= n * fact(n - 1)
= n * (n - 1) * fact(n - 2)
... and so on
= n * (n - 1) * (n - 2) * ... * 4 * 3 * 2 * fact(1)
= n * (n - 1) * (n - 2) * ... * 4 * 3 * 2 * 1 * fact(0)
The factorial of a negative number is not defined, so fact(0) is the smallest version of the factorial problem where our recursion will terminate and return the value directly. So n = 0 is the base case that will return the value 1.
int fact(int n)
{
if(n == 0)
return 1
return n * fact(n - 1)
}
If we draw the flow of recursion for the factorial program, one can find this pattern: we are calling fact(0) last, but it is returning the value first. Similarly, we are calling fact(n) first, but it is returning the value last. Did you find some Last In First Out (LIFO) orders for recursive calls and return values? Yes, you got it right! Behind the scene, the compiler uses a stack data structure to simulate recursion and deliver the correct output. We call this stack: Call Stack!
Order of recursive calls: larger problem to smaller problem
fact(n) -> fact(n - 1) -> ... -> fact(i) -> ... -> fact(1) -> fact(0)
Order of return values: smaller problem to larger problem
fact(0) -> fact(1) -> ...-> fact(i) -> ... -> fact(n - 1) -> fact(n)
How the idea of call stack work in recursion?
Visualization for calculating fact(5) using recursion
Recursive structure: reverse (A[], l, r) = swap(A[l], A[r]) + reverse(A, l+1, r-1)
Base case: if (l >= r) then return
Recurrence relation: T(n) = T(n - 2) + c, Time complexity = O(n)
Recursive structure: GCD(a, b) = GCD(b, a mod b), here a > b
Base case: GCD(a, 0) = a
Recurrence relation: T(n) = T(n/d) + c, where d is a decreasing factor, Time complexity = O(log b)
Recursive structure: fib(n) = fib(n-1) + fib(n-2)
Base case: We have 2 base cases: fib(0) = 0 and fib(1) = 1
Recurrence relation: T(n) = T(n-1) + T(n-2) + c, Time complexity = O(2^n)
Recursive structure: We move a stack of n disks from peg X to Y using peg Z
- Move top n - 1 disks from X to Z
- Move bottom disk from X to Y
- Move top n - 1 disks from Z peg to Y
Base case: If n = 1, move disk from X to Y
Recurrence relation: T(n) = 2 T(n-1) + c, Time complexity = O(2^n)
Recursive structure: binarySearch(A[], l, r, k)
- if A[mid] = k, return mid
- if (A[mid] > k), binarySearch(A[], l, mid - 1, k)
- if (A[mid] < k), binarySearch(A[], mid + 1, r, k)
Base case: If (l > r) then return -1
Recurrence relation: T(n) = T(n/2) + c, Time complexity = O(log n)
Recursive structure: mergeSort (A[], l, r)
- mergeSort(A, l, mid)
- mergeSort(A, mid+1, r)
- merge(A, l, mid, r)
Base case: if (l == r) then return. This is a case of a single-element array.
Recurrence relation: T(n) = 2 T(n/2) + cn, Time complexity = O(n log n)
Recursive structure: quickSort(A[], l, r)
- pivot = partition(A, l, r)
- quickSort(A, l, pivot - 1)
- quickSort(A, pivot + 1, r)
Base case: if (l >= r) then return.
Recurrence relation: T(n) = Sum (i = 0 to n - 1) [T(i) + T(n - i - 1)]/ n, Time complexity = O(nlogn) [Average case analysis]
Recursive structure: reverseList(Node head)
- Node remaining = reverseList(head->next)
- head->next->next = head
- head->next = NULL
- return remaining
Base case: if (head == NULL || head->next == NULL), return head
Recurrence relation: T(n) = T(n - 1) + c, Time complexity = O(n)
Post-order Traversal of a Binary Tree
Recursive structure: postorder(root)
- postorder(root->left)
- postorder(root->right)
- Visit the root
Base case: if(root == NULL), then return
Recurrence relation: T(n) = T(n - 1) + c, Time complexity = O(n)
Print all permutation of a given string
Recursive structure: permute(S[], l, r)
for(i = l to r)
{
swap(S[l], S[i])
permute(S, l + 1, r)
swap(S[l], S[i])
}
Base case: if(l == r) then print(A)
Recurrence relation: T(n) = sum (i = 0 to n - 1) [T(n - i) + c], Time complexity = O(n!)
When we call a recursive function, the return address and arguments are pushed onto the call stack. The stack is finite, so if the recursion is too deep, you'll eventually run out of stack space. This is also called the stack overflow in recursion. In some situations, if the recursive function is tail-recursive, some compilers might optimize the recursive call away by turning it into a jump. Popular reasons for stack overflow error:
Here are two common ways that a recursive implementation can go wrong:
Look for these when you are debugging. On the bright side, an infinite loop in an iterative implementation usually becomes a stack overflow error in a recursive implementation. A buggy recursive program fails faster!
The basic idea of recursion analysis is: Calculate the total number of operations performed by recursion at each recursive call and do the sum to get the overall time complexity. So when recursion is doing constant operation at each recursive call, we just count the total number of recursive calls. Otherwise, the analysis will be a little mathematical if the operation count at each recursive call depends on the input size.
Overall, there are several techniques to analyse recursion: Substitution method, Recursion tree method, and Master theorem.
Explore this blog to learn recursion analysis: Analysis of Recursion in data structure and algorithms
Explore this blog for more details: Iteration vs Recursion comparison
Enjoy learning, Enjoy coding, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.