Recursion means “solving the problem via the solution of the smaller version of the same problem” or “defining a problem in terms of itself”. It is a widely used idea in programming to solve complex problems by breaking them down into simpler ones. In this blog, we’ll go over recursion basics and help you refine an essential programming skill.
Recursion comes up in mathematics frequently, where there are many examples of expressions written in terms of themselves. Calculating the value of nth factorial and nth Fibonacci numbers is the best example of this. 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?
Rules
Solution
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 we use the solution to that smaller instance to solve the original problem. For a recursive algorithm to work, the smaller subproblems must eventually arrive at the base case. In simple words, any recursive algorithm has two parts:
Steps of problem-solving in recursion
Things to keep in mind while working with recursion
Calculate the sum of two numbers using recursion
sum(x, y)
= x, if(y == 0)
= 1 + sum (x, y - 1), if(y > 0)
Calculate the product of two numbers using recursion
product(x, y)
= 0, if(y == 0)
= sum (x, product(x, y - 1), if(y > 0)
Calculate the power of two numbers using recursion
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
Recursive structure
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)
Base case
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.
Recursive pseudocode of nth Factorial
int fact(int n)
{
if(n == 0)
return 1
return n * fact(n - 1)
}
If we draw the flow of recursion for the above 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?
Recursion visualization for calculating fact(5)
Recursion visualization for calculating fact(3)
Image Source: mit.edu
Reverse an array
Finding the GCD of two numbers
Finding the nth Fibonacci
Tower of Hanoi problem
Recursive structure: We move a stack of n disks from peg X to Y using peg Z
Recursive structure: binarySearch(A[], l, r, k)
Recursive structure: mergeSort (A[], l, r)
Recursive structure: quickSort(A[], l, r)
Recursive structure: reverseList(Node head)
Post-order Traversal of a Binary Tree
Recursive structure: postorder(root)
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])
}
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’re 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.
Enjoy learning, Enjoy coding, Enjoy algorithms!
In this blog, we will learn how to use segment trees for efficient point and range updates. For the point update query, update(idx, val), we need to increment the element at the index idx from the original array by val, i.e. arr[idx] = arr[idx] + val. For the range update query, update(l, r, val), we must increment all the elements from index l to r from the original array by val.
Merge sort is one of the fastest comparison-based sorting algorithms, which works on the principle of the divide and conquer approach. The worst and best case time complexity of merge sort is O(nlogn), and space complexity is O(n). It is also the best algorithm for sorting linked lists.
Quicksort is often the best practical choice for sorting because it works remarkably efficiently on average O(nlogn) time complexity. It is also one of the best algorithms to learn problem-solving using recursion and divide and conquer approach. In this blog, we have covered: 1) How quick sort works recursively? 2) Choosing a correct pivot value in the partition algorithm 3) Best, worst, and average-case time complexity analysis 4) Space complexity and essential properties of the quick sort. Explore and Enjoy!
Algorithmic thinking is a method for solving data structure and algorithms problems based on a clear definition of the steps logically and repeatedly. The best idea would be to develop this skill independently from learning programming with proper practice and visualisation. This could help us learn several problem-solving strategies in coding.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.
