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 the basics of recursion and help you to 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 they respond to the person that asked them or the person standing in front of them.
int peopleCount(Person curr)
{
if (noOneBehind(currPerson))
{
return 0
}
else
{
Person personBehind = curr.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()
{
base case
.. .. ...
function() //recursive call
.. .. ...
}
int main()
{
... .. ...
function()
... .. ...
}
In other words — To solve a problem, We solve a subproblem 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, the smaller subproblems must eventually arrive at the base case.
The recursive algorithm has two parts:
Steps to follow
Things to keep in mind
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 power of two numbers using recursion
power(x, y)
= 1, if(y == 0)
= product (x, power(x, y-1), if(y > 0)
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 subproblem 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 you 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 :
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. 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 of the above pseudo-code, 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
Binary search
Recursive structure: binarySearch(A[], l, r, k)
Merge sort
Recursive structure: mergeSort (A[], l, r)
Quick sort
Recursive structure: quickSort(A[], l, r)
Reverse a linked list
Recursive structure: reverseList(Node head)
Post-order traversal of the 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])
}
Mode of implementation
Nature of code error
Analysis of code
Code execution
Code size
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!
Subscribe to get well-designed content on data structures and algorithms, machine learning, system design, oops, and mathematics. enjoy learning!
The binary search is one of the fastest search algorithms, which searches a value in the sorted array in an O(logn) time complexity. Here we search a value using divide and conquer by repeatedly dividing the search interval in half. Moreover, the algorithm for binary search also helps us to solve several coding problems.
EnjoyAlgorithms
In recursive DFS traversals of a binary tree, we have three basic elements to traverse— root, left subtree, and right subtree. The traversal order depends on the order in which we process the root node. Here recursive code is simple and easy to visualize — only one function parameter and 3–4 lines of code. So critical question would be — How can we convert it into iterative code using stack? To simulate the recursive traversal into an iterative traversal, we need to understand the flow of recursive calls.
EnjoyAlgorithms
Explore this blog to answer these questions related to complexity analysis: why time complexity analysis is important? What are the criteria to define the complexity of an algorithm? How do we analyze the time complexity of an algorithm? How do we represent algorithm time complexity in the form of big O notation?
EnjoyAlgorithms
The code structure of a well-designed algorithm using data structure is just like a structure of a good house. So a design of an algorithm must be based on a good understanding of data structures: properties, structure, implementation techniques, and efficiency of its critical operations. The fact is: Data structures are the core building blocks of algorithms and real-life applications.
EnjoyAlgorithms
An array is a contiguous block of memory of the same type of elements where the size is equal to the number of elements in that array, which must be fixed. It is a structure of data such that each element can be efficiently located by its index or memory address.
EnjoyAlgorithms
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!
EnjoyAlgorithms
