Recursion and Iteration are the basic ways to repeatedly execute a given set of instructions in any programming language, and hence, every software engineer must be familiar with these topics. Many software engineering interview problems can be tackled by the simple use of recursion.
In this article, we will cover:
Recursion vs. Iteration: A Simple Example
When to Use Recursion
When to Use Iteration
Key Differences Between Recursion and Iteration
Strengths and Weaknesses of Recursion and Iteration
Cheat Sheet: Recursion vs. Iteration
Problems on Recursion and Iteration
FAQs on Recursion and Iteration
Recursion vs. Iteration: A Simple Example
Before we get into the formal definitions, let’s try and understand these concepts through a simple example.
Recursion is basically a function that calls itself.
Have you watched Christopher Nolan’s Inception? If not, here’s an overview: There are three people — Leo, Tom, and Murphy.
Leo has a machine that lets him enter a target’s dream and can steal information or clues. Leo enters Tom’s dream and realizes the information he needs is not there. Now, while Leo is inside Tom’s dream, he uses his machine to enter Murphy’s dream — a dream within a dream! That's the idea behind recursion.
Note: It’s guaranteed that we either find a set of people or the clue whenever we enter a dream. This way, we never go into infinite recursion.
Iteration is also a way to approach such a scenario in computer programming. The above problem can be solved by iteration too. In this case, we need to know the people who could or could not have the information. Then, we enter each person’s dream and try to find a clue.
In conclusion, recursion and iteration are different ways to execute a set of instructions repeatedly.
Recursion is when a function calls itself within its code, thus repeatedly executing the instructions present inside it.
Iteration is when a loop repeatedly executes the set of instructions like "for" loops and "while" loops.
When to Use Recursion?
Sometimes we encounter a problem that is too complex to solve directly. In most cases, we try to break such problems down into smaller pieces. Then, we can find a way to solve these smaller pieces and then build up a solution to the entire problem. This is the entire idea behind recursion.
Recursion is when a function calls itself directly or indirectly, and the function calling itself is called a recursive function. It is mainly used when the solution to a bigger problem can be expressed in terms of smaller problems.
To terminate the recursion, we use some conditions so that the function knows when not to make any further recursive call to itself and return; otherwise, it will lead to infinite recursion once the function is called. Such conditions are called base conditions in recursion.
For example, let's define steps for Leo in our example above to get the clue he needs:
Step 1: If you have found the clue, stop; else, go to step 2.
Step 2: Find a target to enter their dream for finding clues. Go to step 3.
Step 3: Use the machine to enter their dream. Go to step 1.
We can see the recursive solution for finding the clue can be written in three steps. The base case here is if we have already found the clue, then we simply stop the recursion. Else, we enter some other target’s dream and redo the entire algorithm.
Wondering how many times the function can call itself?
The local variables and parameters being passed by value are newly created each time the function calls itself. They are stored in stack memory whenever a recursive call is made and are deallocated when the execution of the current function call is complete. The state of the functions is also stored in stack memory. Thus, each recursive call consumes some amount of memory on the stack. In case of infinite recursion or when recursion depth is large enough to exhaust the memory on the stack, it will cause a stack overflow error.
When to Use Iteration?
Iteration is when we execute a set of instructions repeatedly until the condition controlling the loop becomes false. It includes initialization, comparison, executing statements inside the iteration, and updating the control variable.
In iteration, it is necessary to have the right controlling condition; else, the program may go in an infinite loop.
For example, let’s write an iterative program to help Leo find his clue:
Step 1: Create an initial list of people who are targets.
Step 2: While the list is not empty, get a target from the list and enter his dream. Go to step 3.
Step 3: If you do not get the clue, go to step 2; else, go to step 4.
Step 4: Congratulations! You found the clue!
Here, the while statement in Step 2 is the controlling statement, which will decide when the loop will end.
Key Differences Between Recursion and Iteration
Recursion and iteration are both different ways to execute a set of instructions repeatedly. The main difference between these two is that in recursion, we use function calls to execute the statements repeatedly inside the function body, while in iteration, we use loops like “for” and “while” to do the same.
Iteration is faster and more space-efficient than recursion. So why do we even need recursion? The reason is simple — it's easier to code a recursive approach for a given problem. Try doing inorder tree traversal using recursion and iteration both.
Example
Let’s look at a simple factorial program implemented using recursion and iteration.
Recursion
For Factorial we can write it as the below formula :
Factorial ( n ) = n * Factorial ( n-1 ) , for all n>=1 ,
Factorial ( 0 ) = 1 , Base Case
So we can write this in a recursive way where if we reach n = 0, then that’s our base case; else, we make the recursive call for n-1.
Explanation:
Here, the fact function uses recursion to calculate the factorial of a given number.
We can write factorial(n) as n*factorial(n-1), which is the required recursive relation.
n=0 is the base case, and we simply return 1 if it’s true.
#include<bits/stdc++.h>
using namespace std;
// Recursive function to find factorial of given number.
int fact(int n) {
// Base condition
if (n == 0) {
return 1;
}
// Recursive call
return n * fact(n-1);
}
int main() {
int n = 5;
cout << n << " factorial = " << fact(n);
return 0;
}
Output:
5 factorial = 120
Iteration
Iteration can be simply written by using the formula for factorial:
Factorial ( n ) = 1 * 2 * 3 * … * (n-2) * ( n-1 ) * n
Explanation:
Here, we maintain a variable answer in which we will store the final result.
We initialize the control variable i = 2 and then multiply answer by it.
After each iteration, i is incremented by 1 until it becomes greater than n.
#include<bits/stdc++.h>
using namespace std;
// Factorial of given number using iteration.
int factorial(int n) {
int answer = 1;
// initialization; termination condition; control variable update;
for(int i = 2; i <= n; i++) {
answer *= i;
}
return answer;
}
int main() {
int n = 5;
cout << n << " factorial = " << factorial(n);
return 0;
}
Output:
5 factorial = 120
Time Complexity
There are O(N) recursive calls in our recursive approach, and each call uses O(1) operations. Thus, the time complexity of factorial using recursion is O(N).
There are O(N) iterations of the loop in our iterative approach, so its time complexity is also O(N).
Though both the programs’ theoretical time complexity is the same, a recursive program will take more time to execute due to the overhead of function calls, which is much higher than that of iteration.
Space Complexity
In the recursive program, due to each recursive call, some memory gets allocated in the stack to store parameters and local variables. As there are O(N) recursive calls, the space complexity using recursion is O(N).
No extra memory gets allocated in the iterative program, so its space complexity is O(1).
Strengths and Weaknesses of Recursion and Iteration
Iteration
Strengths:
Iteration can be used to repeatedly execute a set of statements without the overhead of function calls and without using stack memory.
Iteration is faster and more efficient than recursion.
It's easier to optimize iterative codes, and they generally have polynomial time complexity.
They are used to iterate over the elements present in data structures like an array, set, map, etc.
If the iteration count is known, we can use for loops; else, we can use while loops, which terminate when the controlling condition becomes false.
Weaknesses:
In loops, we can go only in one direction, i.e., we can’t go or transfer data from the current state to the previous state that has already been executed.
It’s difficult to traverse trees/graphs using loops.
Only limited information can be passed from one iteration to another, while in recursion, we can pass as many parameters as we need.
Recursion
Strengths:
It’s easier to code the solution using recursion when the solution of the current problem is dependent on the solution of smaller similar problems. - fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) - factorial(n) = n * factorial(n-1)
Recursive codes are smaller and easier to understand.
We can pass information to the next state in the form of parameters and return information to the previous state in the form of the return value.
It’s a lot easier to perform operations on trees and graphs using recursion.
Weaknesses:
The simplicity of recursion comes at the cost of time and space efficiency.
It is much slower than iteration due to the overhead of function calls and control shift from one function to another.
It requires extra memory on the stack for each recursive call. This memory gets deallocated when function execution is over.
It is difficult to optimize a recursive code, and they generally have higher time complexity than iterative codes due to overlapping subproblems.
Cheat Sheet: Recursion vs. Iteration
Problems on Recursion and Iteration
Here are a few examples of the kind of problems you can expect on recursion and iteration during tech interviews:
Write a program to find the n-th Fibonacci number, first using recursion and then using iteration. Compare the time and space complexities of both the solutions.
Write a program to solve the famous Tower of Hanoi puzzle using recursion. Try solving it using iteration.
Write a program for preorder, postorder and inorder traversal of a tree using both iteration and recursion.
FAQs on Recursion and Iteration
Question 1: How to use memoization in a program to find the n-th Fibonacci number using recursion?
Answer: Let us first look at the overlapping subproblems:
We can see that fib(3) is called two times, fib(2) is called three times, and so on. If we had stored the value of fib(2), fib(3), we would have directly used it instead of computing it again. Imagine calling fib(n) function for n = 100 and the number of function calls we can prevent by just storing the value when we first calculate it.
To do this, we can use an array say ‘mem’ of size n such that mem[i] = -1 if the value of fib(i) hasn’t been calculated yet, else mem[i] = fib(i). After this, whenever we need to calculate fib(i), we directly pick its value from the ‘mem’ array.
Time complexity before memoization: O(2^n) Time complexity after memoization: O(n) Space complexity before and after memoization: O(n)
Question 2: How to check if the given Binary Tree is a Binary Search Tree given all elements are distinct.
Answer: Do the inorder traversal of the given tree and store the result in an array. If the array obtained is sorted, the given tree is a BST; else, it is not a BST.
Time complexity: O(n), n is the number of nodes in the given binary tree. Space complexity: O(n)
We can, however, optimize the space complexity by keeping track of the previously visited node. If the current node’s value is less than the value of the previous node, then the given binary tree is not a BST.
Question 3: Write a program to print the elements of the given linked list in reverse order.
Answer: While traversing a linked list, if we simply print the current element and move to the next element, we get the linked list in forward order. So rather than printing right away, we can move to the next element until we encounter the list’s end. Once we reach the end of the list, we return to the previous recursion call and print our element. Thus we print all elements in reverse order. Below is the pseudocode for it:
If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
.png)
