Iteration and recursion are both techniques that you can use for implementing solutions in a programming language. I look at both of them as a way of thinking about a problem and solving it. The most important thing to keep in mind before we start discussing them is:
For any problem that can be solved via iteration, there is a corresponding recursive solution and vice versa.

For a programmer, it is important to understand both techniques, and be aware of their differences and when to resort to one technique in favor of the other. Let's start!
Iteration
Iteration
is simply the repetition
of a block of code in a program. In many cases, we need a control variable
to implement iteration. Alternatively, we can repeatedly execute a block of code until a certain stopping criterion is met.
Generally you can implement iteration using for, while or do-while loop constructs (in some programming languages we have the alternate repeat construct). Let's look at an example pseudo-code, where we print numbers from 1 to 5 using a control variable i.
As the values of i
change in the loop, the numbers 1, 2, 3, 4, 5
are printed. The loop is executed as long as the condition i <= 5
holds true.
xxxxxxxxxx
let i = 1; // Initial value of control variable
// Repeat the next block till condition i <= 5 is true
while (i <= 5) {
console.log(i); // Print i
i = i + 1; // Increment i by 1
}
Recursion
Recursion
is a technique based on the divide and conquer
principle. That principle calls for us to define the solution of a bigger problem in terms of the solution of a smaller version of itself.
In a programming language, a recursive function is one that calls itself. Let's look at the pseudo-code of a recursive function that prints the numbers from 1
to 5
. You can invoke the function printList
like printList(1)
.
The code is pretty cool as it will, like our iterative counterpart, also print the numbers 1, 2, 3, 4, 5
. printList
is a recursive function as it calls itself. We'll learn how it works in a bit.
xxxxxxxxxx
function printList(i) {
// Base case: If i is greater than 5, return without doing anything
if (i > 5) {
return; // Do nothing
}
// Recursive case: Print the value of i
console.log(i);
// Call the function with i + 1
printList(i + 1);
}
Two Parts of a Recursive Solution
Recursion
is implemented by defining two scenarios, both of these are marked in the printList
function:
Base case: This is the
non-recursive
case (the part that doesn't trigger another call) and defines when to stop (or the smallest version of the problem).General case / Recursive case: Defines how to solve the problem in terms of a smaller version of itself. Each general case should get you "closer" to the base case.
Are you sure you're getting this? Is this statement true or false?
In theory, if a base case is not defined for a recursive function, the code will raise an exception.
Press true if you believe the statement is correct, or false otherwise.
How Recursion Works: The Activation Stack
The pseudo-code for the printList
function can only be implemented in what we call "a stack based language". These languages keep track of all the functions, which have been invoked at runtime using a data structure called the activation stack
. They allow functions to call themselves, by saving their state (local variables
and parameters
) on a stack, and invoking them again.
Everytime a function is called, its entire state including its local variables and pass by value
parameters are saved as a record on the stack. When the function exits, its corresponding record is popped off this stack.
A recursive
call would therefore push a record of the function on the stack. Then, the base case would start a process called "unwinding recursion" and slowly the records would be popped off the stack.

The diagram above shows the activation stack for printList
. Note how the system preserves various copies of the printList
function, with each copy having its own value of the variable i
. The stack is built until the condition for the base case holds true. After that the records from the stack are popped off.
Reversed
What happens if you reverse the statements in printList
?
Well, now the function is being called before printing the value of i
. So the values are printed during the "unwind recursion" phase, after the base case is invoked. This would print the values in reverse (in other words, 5, 4, 3, 2, 1
).
xxxxxxxxxx
function printList(i) {
// base case
if (i > 5) {
return; // do nothing
}
// recursive case
printList(i + 1);
console.log(i);
}
​
printList(1);
Factorial
Now that we understand both iteration and recursion, let's look at how both of them work.
As we know factorial of a number is defined as:
n! = n(n-1)(n-2)...1
or in other words:
n! = n(n-1)!
Let's now implement both an iterative and recursive solution for factorial in C++.
Both solutions look intuitive and easy to understand. The iterative version has a control variable i
, which controls the loop so that the loop runs n
times. For the iterative solution, we know in advance exactly how many times the loop would run.
The recursive version uses the second definition: n! = n * (n - 1)!
, which is naturally a recursive
definition. It defines the factorial of n
in terms of the factorial of a smaller version (n - 1)
. We don't need to specify in advance, how many times the loop will run.
xxxxxxxxxx
// Iterative
function factorialIterative(n) {
let result = 1;
for (let i = n; i >= 1; i--) {
result = result * i;
}
return result;
}
​
// Recursive
function factorialRecursive(n) {
let result = 0;
​
if (n == 1)
// base case: n==1
result = 1;
// recursive case
else result = n * factorialRecursive(n - 1);
​
return result;
}
​
factorialIterative(4);
factorialRecursive(4);
Working of Factorial: Iterative vs. Recursive Case
Look at the diagrams below to see the "behind the scenes" portion of the activation stack for both the iterative and recursive cases:

The most important thing to note is that the iterative version has only one function record on the activation stack
. For the recursive cases, there are 4 records of the function on the activation stack until the recursion starts to unwind.
So imagine what would happen if you were to call factorial
for a larger number like 10
or 20
. So many records on the activation stack is a strain on the system's memory! There is also the extra overhead of function calling, saving its state, and maintaining the activation stack.
If you are using a programming language like C++
or Java
, then go for the iterative solution as it would run in constant memory.
Build your intuition. Click the correct answer from the options.
Which of the following statements are correct?
Click the option that best answers the question.
- Recursion should be used when the problem is repetitive
- Iteration cannot be used on every recursive problem
- Iteration uses activation stack
- Recursion uses less memory as compared to iteration
Quick Sort: Think Recursively!
From the factorial example, we learned not to use recursion
. So why is every computer scientist in such awe with regards to this technique?
Well, the answer is that if you look at some problems, you'll find that they are naturally recursive
in nature. The solution to such problems is conceptually easier to implement via recursion, and harder to implement via iteration. Let's analyze the pseudo-code for quick sort
first, and then we'll see its various solutions. Note: I am using pivot
as the middle item
of the array
.
See how the solution says that we will "apply the sort to a smaller version of the array" to sort the entire array. The following diagram also called the recursion tree shows the working of quickSort
.

xxxxxxxxxx
quickSort
input: array
output: sorted array
​
Base case:
1. If the array size<=1 then the array is sorted
Recursive case:
1. Find the pivot of the array
2. Adjust all items less than pivot on the left side of pivot
3. Adjust all items greater than pivot on the right side of pivot
4. quickSort the subarray to the left of pivot
5. quickSort the subarray to the right of pivot
Quick Sort Implementation
The recursive version of quick sort is very easy to implement, and is shown in the right box. See how elegant and easy it is?
Most people looking at the code can meaningfully understand the "concept" behind quick sort
. It first adjusts items around the pivot, and then calls quickSort
recursively on both left and right subarrays.
xxxxxxxxxx
console.log(vect);
function exchange(a, i, j) {
let temp = a[i];
a[i] = a[j];
a[j] = temp;
}
​
function adjust(A, start, end, pivot) {
let a = start, b = end;
let stop = false;
while (!stop) {
while (a < pivot && A[a] <= A[pivot])
a++;
while (b > pivot && A[b] >= A[pivot])
b--;
if (a >= pivot && b <= pivot)
stop = true;
else {
exchange(A, a, b);
if (a === pivot)
pivot = b;
else if (b === pivot)
pivot = a;
}
}
}
​
function quickSortRecursive(A, start, end) {
if (end - start < 0)
return;
But What About Iterative?
Now let's think of the iterative version. It's not as straightforward to implement!
We can apply the pivot and adjustment of items around the pivot, only on one subarray
at a time. If we work with the left subarray, then we need to store the indices
of the right subarray to be used later for repeating the process. This necessitates the implementation of our own stack that will maintain the indices of left and right subarrays to work with, instead of using the implicitly built system activation stack for recursive functions.
In the code here for the iterative version of quickSort
, we have two stacks of the same size. One holds the start index of the subarray and the other holds the end index of the subarray. Once values are adjusted around the pivot for one subarray, the other subarray's start and end indices are popped from the stack.
xxxxxxxxxx
console.log(vect);
function exchange(a, i, j) {
let temp = a[i];
a[i] = a[j];
a[j] = temp;
}
​
function adjust(A, start, end, pivot) {
let a = start, b = end;
let stop = false;
while (!stop) {
while (a < pivot && A[a] <= A[pivot])
a++;
while (b > pivot && A[b] >= A[pivot])
b--;
if (a >= pivot && b <= pivot)
stop = true;
else {
exchange(A, a, b);
if (a === pivot)
pivot = b;
else if (b === pivot)
pivot = a;
}
}
}
​
function quickSortIterative(A, start, end) {
let startIndex = [];
let endIndex = [];
Iteration or Recursion for Quick Sort?
Of course, the main question now is: which solution to go for, iterative
or recursive
?
I would still advise you to go for the iterative
solution. Imagine sorting an array with a million items. The system stack would need to save a significant number of records of the quick sort
function. It opens you up to problems, like running out of memory, resulting in segmentation faults, etc.
Having said that, the recursive
version is so much easier to write and understand. So I would go for implementing a recursive version first (and for interviews), and then thinking about how to implement it iteratively using your own stack (optimize later).
Towers of Hanoi
The last problem that I would like to talk about in this tutorial is the Towers of Hanoi
game, which again is an example of a wonderful naturally recursive problem.
The Problem
You have 3
shelves (A, B, C)
and N
disks. Each disk is a different size and stacked such that a smaller disk is placed on top of a larger disk.
You are not allowed to place a bigger disk on top of a smaller disk. The target of the game is to move all disks from one shelf to another, using the third one as an intermediate storage location.
At any point you are not allowed to violate the rule of the game. Thus, a smaller disk is always on top of a bigger disk.
Below is an example of 3
disks of different sizes. I have made them all in a different color. The starting and goal configurations are shown in this figure.

An Awesome Recursive Solution
The best way to figure out a solution is to think logically and recursively. Break down the problem into a smaller version of itself.
If we can somehow figure out how to move N-1
disks from source shelf to intermediate shelf, using the destination as an intermediate location, then we can move the biggest disk from source to destination. Next, we can move the N-1
disks from intermediate shelf to the target, using source shelf as intermediate location. The diagram below will help in visualizing this.

The pseudo-code is therefore very simple.
xxxxxxxxxx
Recurisve routine: Hanoi
Input: source shelf, target shelf, intermediate shelf, N disks placed on source shelf
Target: N disks placed on target shelf
​
Base case:
1. If there are zero disks then stop.
Recursive case:
1. Move (N-1) disks from source to intermediate using destination as intermediate shelf
2. Shift the last disk from source to destination
3. Move (N-1) disks from intermediate to destination using source as intermediate shelf
Recursion Tree for Hanoi
Figure below shows the recursion tree for a 3 disk problem

Collect together all the shift moves to have the final solution:

Attached is the beautiful recursive code for Towers of Hanoi
done in C++
using the pseudo-code given previously. As you can see, it is a direct translation of the pseudo-code we wrote beforehand.
xxxxxxxxxx
function shift(shelf1, shelf2) {
console.log("Shift from " + shelf1 + " to " + shelf2);
}
​
function Hanoi(N, source, destination, intermediate) {
// base case
if (N === 0)
return;
// recursive case
Hanoi(N - 1, source, intermediate, destination);
shift(source, destination);
Hanoi(N - 1, intermediate, destination, source);
}
​
// example call for the illustrated problem
Hanoi(3, 'A', 'B', 'C');
Iterative Code for Towers of Hanoi
So are you up for the challenge? Of course you are! We have to figure out an iterative solution.
The best thing we can do is define a stack for source
, destination
, intermediate
and N
. You can see that steps 1, 2, and 3 of the recursive case have to be executed in the same order.
This means we first push whatever corresponds to step 3 (to be executed last). Next, we push whatever corresponds to step 2 of the recursive case. Lastly, push whatever corresponds to step 1 of the recursive case.
This is typically how you would approach the solution of a recursive solution via iteration using a temporary stack. So here is a very elegant iterative
solution for Towers of Hanoi
.
xxxxxxxxxx
h.solve(3, 'A', 'B', 'C');
class HanoiIterative {
constructor() {
this.sourceStack = [];
this.destinationStack = [];
this.intermediateStack = [];
this.NStack = [];
}
​
shift(shelf1, shelf2) {
console.log("Shift from " + shelf1 + " to " + shelf2);
}
​
pushStacks(s, d, i, n) {
this.sourceStack.push(s);
this.destinationStack.push(d);
this.intermediateStack.push(i);
this.NStack.push(n);
}
​
popStacks() {
this.sourceStack.pop();
this.destinationStack.pop();
this.intermediateStack.pop();
this.NStack.pop();
}
​
solve(N, source, destination, intermediate) {
if (N <= 0)
return;
Let's test your knowledge. Fill in the missing part by typing it in.
How many recursive calls will be required to check if the number 37 is prime using recursion?
Write the missing line below.
Take Away Lesson
Even though problems like Towers of Hanoi
are naturally recursive problems with easy implementations using recursion, I still advise you to do their final implementation in languages like Java, C++ etc. using the iterative technique.
This way only one activation record would be pushed on the stack for the iterative function. However, when given such problems, always write the recursive mathematical expression or recursive pseudo-code for them, and then figure out how to implement them iteratively.
Iterative
functions would be faster and more efficient compared to their recursive counterparts because of of the lack of activation stack
overhead.
Some functional programming languages like LISP
have built in techniques to handle tail recursion without building a large activation stack. They are pretty cool, in the sense that they allow you to code everything using recursion
, without the extra overhead of activation stack.
I hope you enjoyed this lesson as much as I enjoyed creating it.
Let's test your knowledge. Could you figure out the right sequence for this list?
How would you replace recursion with iteration? Select the correct order.
Press the below buttons in the order in which they should occur. Click on them again to un-select.
Options:
- Remove an element from the array
- Initialize a loop
- Initialize an empty array for storing elements
- Perform the necessary calculation
- Add an element to array
One Pager Cheat Sheet
- Both iteration and
recursion
can be used to solve programming problems, but an important thing to keep in mind is that for any problem that can be solved via iteration, there is a corresponding recursive solution and vice versa. - Iteration is the
repetition
of a block of code usingcontrol variables
or a stopping criterion, typically in the form of for, while or do-while loop constructs. - A recursive function is one that calls itself, such as the
printList
function which uses thedivide and conquer
principle to print the numbers1
to5
. - The
printList
function implementsrecursion
by defining a base case (the non-recursive part) and a general / recursive case (defining how to solve the problem in terms of a smaller version of itself). - The execution of a recursive function
without a base case
will not raise an exception, but can lead tostack overflow
if the maximum number of recursive calls is exceeded. - Recursion is a technique that enables a function to save its
local variables
andparameters
on anactivation stack
, which is thenpopped off
when the function exits or thebase case
is reached. - The
printList
function will print the values in reverse,5, 4, 3, 2, 1
, when the statements are reversed, which happens during the "unwind recursion" phase after the base case is invoked. - We can calculate the factorial of a number using either an
iterative
orrecursive
implementation in C++. - The
iterative
solution is more efficient for programming languages such asC++
orJava
as it runs in constant memory, compared to therecursive
solutions which generates 4 records on theactivation stack
for each call. - The recursive version of the factorial function takes up more
memory
due to increasedactivation stack
records, while being less optimal in languages likeC++
andJava
. - Quick Sort is a naturally
recursive
sorting algorithm that divides the entire array into smaller pieces, and is conceptually easier to implement via recursion. - The clear concept behind
Quick Sort
is easily understood from the elegant and simple recursive version of the algorithm, which adjusts elements around a pivot before callingquickSort
recursively on both subarrays. - We need to
implement our own stack
to maintain theindices
of the left and right subarrays for the iterative version ofquickSort
. - Of course, the main question now is: which solution to go for,
iterative
orrecursive
, and I would still advise you to go for theiterative
solution to avoid segmentation faults while therecursive
version is easier to write and understand. - The
Towers of Hanoi
game is an example of a naturally recursive problem in which you move disks from one shelf to another while following a rule that a smaller disk cannot be placed on top of a larger disk. - Break down the problem into a smaller version of itself to solve it recursively using an intermediate location when moving disks.
- The figure shows the Recursion Tree for the 3 disk Towers of Hanoi problem, with the final solution being derived from a direct translation of the pseudo-code in
C++
. - We can solve the
Towers of Hanoi
problem using an iterative approach by pushing step 3, then 2 and then 1 onto a temporary stack. - The number of recursive calls required to check if the number 37 is prime using recursion is three, due to the
base case
and subsequent checks fordivisibility
. Using an iterative technique instead of recursion can be more efficient when solving problems like Towers of Hanoi since there would be no overhead associated with the activation stack.
- Replace recursion with iteration by initializing an empty array, iterating through it with a loop, removing each element for processing, making the relevant calculations, and finally, adding it back to the array.