Problem Solving With Recursion vs. Iteration
Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.
Introduction
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!
0Iteration
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.
```cpp
#include <iostream>
int main() {
int i = 1; // Initial value of control variable
// Repeat the next block till condition i <= 5 is true
while (i <= 5) {
std::cout << i << std::endl; // Print i
i = i + 1; // Increment i by 1
}
return 0;
}
```
```python
i = 1 # Initial value of control variable
# Repeat the next block till condition i <= 5 is true
while i <= 5:
print(i) # Print i
i = i + 1 # Increment i by 1
```
```java
public class Main {
public static void main(String[] args) {
int i = 1; // Initial value of control variable
// Repeat the next block till condition i <= 5 is true
while (i <= 5) {
System.out.println(i); // Print i
i = i + 1; // Increment i by 1
}
}
}
```
```javascript
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
}
```
```csharp
class Program {
static void Main(string[] args) {
int i = 1; // Initial value of control variable
// Repeat the next block till condition i <= 5 is true
while (i <= 5) {
Console.WriteLine(i); // Print i
i = i + 1; // Increment i by 1
}
}
}
```
```go
package main
import "fmt"
func main() {
i := 1 // Initial value of control variable
// Repeat the next block till condition i <= 5 is true
for i <= 5 {
fmt.Println(i) // Print i
i = i + 1 // Increment i by 1
}
}
```Recursion
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.
```cpp
void printList(int 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
std::cout << i << std::endl;
// Call the function with i + 1
printList(i + 1);
}
```
```java
public class Main {
public static void printList(int 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
System.out.println(i);
// Call the function with i + 1
printList(i + 1);
}
public static void main(String[] args) {
// Example call to printList starting from 1
printList(1);
}
}
```
```javascript
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);
}
```
```python
def 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
print(i)
# Call the function with i + 1
printList(i + 1)
```
```csharp
public static void PrintList(int 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.WriteLine(i);
// Call the function with i + 1
PrintList(i + 1);
}
```
```go
package main
import "fmt"
func printList(i int) {
// 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
fmt.Println(i)
// Call the function with i + 1
printList(i + 1)
}
func main() {
// Example call to printList starting from 1
printList(1)
}
```Loop Vs Call Chain
Both versions print 1, 2, 3, 4, 5, but they control progress differently.
In iteration, one frame keeps changing i. In recursion, each call creates a new frame with its own i, until the base case stops the chain.
Same Goal, Different Control
Both versions print 1 through 5, but the control mechanism is different.
-
Iteration: one frame stays active while
ichanges. -
Recursion: each call creates a new frame with its own
i, until the base case stops the chain.
Use the visual to track where the next value comes from.
Two Parts Of A Recursive Solution
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-recursivecase (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.
True or False
In theory, if a base case is not defined for a recursive function, the code will raise an exception.
How Recursion Works The Activation Stack
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
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).
```java
public class Main {
public static void main(String[] args) {
printList(1);
}
static void printList(int i) {
// base case
if (i > 5) {
return; // do nothing
}
// recursive case
printList(i + 1);
System.out.print(i);
}
}
```
```javascript
function printList(i) {
// base case
if (i > 5) {
return; // do nothing
}
// recursive case
printList(i + 1);
console.log(i);
}
printList(1);
```
```python
def printList(i):
# base case
if i > 5:
return # do nothing
# recursive case
printList(i + 1)
print(i)
printList(1)
```
```cpp
#include <iostream>
void printList(int i) {
// base case
if (i > 5) {
return; // do nothing
}
// recursive case
printList(i + 1);
std::cout << i;
}
int main() {
printList(1);
return 0;
}
```
```csharp
class Program {
static void Main(string[] args) {
PrintList(1);
}
static void PrintList(int i) {
// base case
if (i > 5) {
return; // do nothing
}
// recursive case
PrintList(i + 1);
Console.Write(i);
}
}
```
```go
package main
import "fmt"
func main() {
printList(1)
}
func printList(i int) {
// base case
if i > 5 {
return // do nothing
}
// recursive case
printList(i + 1)
fmt.Print(i)
}
```Factorial
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.
```cpp
#include <iostream>
// Iterative
int factorialIterative(int n) {
int result = 1;
for (int i = n; i >= 1; i--) {
result = result * i;
}
return result;
}
// Recursive
int factorialRecursive(int n) {
int result = 0;
if (n == 1)
// base case: n==1
result = 1;
else
// recursive case
result = n * factorialRecursive(n - 1);
return result;
}
int main() {
std::cout << factorialIterative(4) << '\n';
std::cout << factorialRecursive(4);
return 0;
}
```
```js
// 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);
```
```java
// Iterative
public static int factorialIterative(int n) {
int result = 1;
for (int i = n; i >= 1; i--) {
result = result * i;
}
return result;
}
// Recursive
public static int factorialRecursive(int n) {
int result = 0;
if (n == 1)
// base case: n==1
result = 1;
else
// recursive case
result = n * factorialRecursive(n - 1);
return result;
}
public static void main(String[] args) {
System.out.println(factorialIterative(4));
System.out.println(factorialRecursive(4));
}
```
```python
# Iterative
def factorialIterative(n):
result = 1
for i in range(n, 0, -1):
result = result * i
return result
# Recursive
def factorialRecursive(n):
result = 0
if n == 1:
# base case: n==1
result = 1
else:
# recursive case
result = n * factorialRecursive(n - 1)
return result
print(factorialIterative(4))
print(factorialRecursive(4))
```
```csharp
// Iterative
public static int factorialIterative(int n) {
int result = 1;
for (int i = n; i >= 1; i--) {
result = result * i;
}
return result;
}
// Recursive
public static int factorialRecursive(int n) {
int result = 0;
if (n == 1)
// base case: n==1
result = 1;
else
// recursive case
result = n * factorialRecursive(n - 1);
return result;
}
public static void Main(string[] args) {
Console.WriteLine(factorialIterative(4));
Console.WriteLine(factorialRecursive(4));
}
```
```go
// Iterative
func factorialIterative(n int) int {
result := 1
for i := n; i >= 1; i-- {
result = result * i
}
return result
}
// Recursive
func factorialRecursive(n int) int {
var result int
if n == 1 {
// base case: n==1
result = 1
} else {
// recursive case
result = n * factorialRecursive(n - 1)
}
return result
}
func main() {
fmt.Println(factorialIterative(4))
fmt.Println(factorialRecursive(4))
}
```Call Down, Return Up
The order of work depends on where the action happens.
If you print before the recursive call, values appear while the stack grows. If you print after the recursive call, values appear while the stack unwinds.
Watch The Unwind
The key recursion move is not just going down to the base case. It is also what happens while calls return.
For reversed printing, the output happens during the unwind. For factorial, the multiplication also happens during the unwind: 4! waits for 3!, which waits for 2!, and so on.
Working Of Factorial Iterative Vs. Recursive Case
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.
Multiple Choice
Which of the following statements are correct?
Quick Sort Think Recursively!
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.
```text
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
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.
```cpp
#include <iostream>
#include <vector>
using namespace std;
// a few helper functions
void exchange(int & a, int & b) {
int temp = a;
a = b;
b = temp;
}
// adjust items so that values less than value at pivot are on left
// and values greater than value at pivot are on right of pivot
// return the new index of pivot via pass by reference parameter
void adjust(vector < int > & A, int start, int end, int & pivot) {
int a = start, b = end;
bool stop = false;
while (!stop) { // move a
while (a < pivot && A[a] <= A[pivot])
a++;
// move b
while (b > pivot && A[b] >= A[pivot])
b--;
if (a >= pivot && b <= pivot)
stop = true;
else {
exchange(A[a], A[b]);
if (a == pivot)
pivot = b;
else if (b == pivot)
pivot = a;
}
}
}
// start and end are indices
void quickSortRecursive(vector < int > & A, int start, int end) {
// base case: size<=1
if (end - start < 0)
return;
int pivot = (start + end) / 2;
// adjust around the pivot
adjust(A, start, end, pivot);
// apply on left subarray
quickSortRecursive(A, start, pivot - 1);
// apply on right subarray
quickSortRecursive(A, pivot + 1, end);
// uncomment the line below to understand whats going on
// cout << start << " " << end << " " << pivot << "\n";
}
// main function to call
void quickSort(vector < int > & A) {
quickSortRecursive(A, 0, A.size() - 1);
}
int main() {
vector<int> vect{7, 6, 0, -4, 3};
quickSort(vect);
}
```
```java
import java.util.Arrays;
public class Main {
// a few helper functions
public static void exchange(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void adjust(int[] A, int start, int end, int pivot) {
int a = start, b = end;
boolean 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;
}
}
}
public static void quickSortRecursive(int[] A, int start, int end) {
if (end - start < 0)
return;
int pivot = (start + end) / 2;
adjust(A, start, end, pivot);
quickSortRecursive(A, start, pivot - 1);
quickSortRecursive(A, pivot + 1, end);
}
public static void quickSort(int[] A) {
quickSortRecursive(A, 0, A.length - 1);
}
public static void main(String[] args) {
int[] vect = {7, 6, 0, -4, 3};
quickSort(vect);
System.out.println(Arrays.toString(vect));
}
}
```
```javascript
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;
let pivot = Math.floor((start + end) / 2);
adjust(A, start, end, pivot);
quickSortRecursive(A, start, pivot - 1);
quickSortRecursive(A, pivot + 1, end);
}
function quickSort(A) {
quickSortRecursive(A, 0, A.length - 1);
}
let vect = [7, 6, 0, -4, 3];
quickSort(vect);
console.log(vect);
```
```python
def exchange(a, i, j):
temp = a[i]
a[i] = a[j]
a[j] = temp
def adjust(A, start, end, pivot):
a, b = start, end
stop = False
while not stop:
while a < pivot and A[a] <= A[pivot]:
a += 1
while b > pivot and A[b] >= A[pivot]:
b -= 1
if a >= pivot and b <= pivot:
stop = True
else:
exchange(A, a, b)
if a == pivot:
pivot = b
elif b == pivot:
pivot = a
def quickSortRecursive(A, start, end):
if end - start < 0:
return
pivot = (start + end) // 2
adjust(A, start, end, pivot)
quickSortRecursive(A, start, pivot - 1)
quickSortRecursive(A, pivot + 1, end)
def quickSort(A):
quickSortRecursive(A, 0, len(A) - 1)
vect = [7, 6, 0, -4, 3]
quickSort(vect)
print(vect)
```
```csharp
using System;
class Program {
public static void Exchange(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void Adjust(int[] A, int start, int end, ref int pivot) {
int a = start, b = end;
bool 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;
}
}
}
public static void QuickSortRecursive(int[] A, int start, int end) {
if (end - start < 0)
return;
int pivot = (start + end) / 2;
Adjust(A, start, end, ref pivot);
QuickSortRecursive(A, start, pivot - 1);
QuickSortRecursive(A, pivot + 1, end);
}
public static void QuickSort(int[] A) {
QuickSortRecursive(A, 0, A.Length - 1);
}
public static void Main(string[] args) {
int[] vect = {7, 6, 0, -4, 3};
QuickSort(vect);
Console.WriteLine(string.Join(", ", vect));
}
}
```
```go
package main
import "fmt"
func exchange(a []int, i, j int) {
temp := a[i]
a[i] = a[j]
a[j] = temp
}
func adjust(A []int, start, end int, pivot *int) {
a, b := start, end
stop := false
for !stop {
for a < *pivot && A[a] <= A[*pivot] {
a++
}
for 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
}
}
}
}
func quickSortRecursive(A []int, start, end int) {
if end-start < 0 {
return
}
pivot := (start + end) / 2
adjust(A, start, end, &pivot)
quickSortRecursive(A, start, pivot-1)
quickSortRecursive(A, pivot+1, end)
}
func quickSort(A []int) {
quickSortRecursive(A, 0, len(A)-1)
}
func main() {
vect := []int{7, 6, 0, -4, 3}
quickSort(vect)
fmt.Println(vect)
}
```But What About Iterative?
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.
```cpp
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// a few helper functions
void exchange(int & a, int & b) {
int temp = a;
a = b;
b = temp;
}
// adjust items so that values less than value at pivot are on left
// and values greater than value at pivot are on right of pivot
// return the new index of pivot via pass by reference parameter
void adjust(vector < int > & A, int start, int end, int & pivot) {
int a = start, b = end;
bool stop = false;
while (!stop) { // move a
while (a < pivot && A[a] <= A[pivot])
a++;
// move b
while (b > pivot && A[b] >= A[pivot])
b--;
if (a >= pivot && b <= pivot)
stop = true;
else {
exchange(A[a], A[b]);
if (a == pivot)
pivot = b;
else if (b == pivot)
pivot = a;
}
}
}
// start and end are indices
void quickSortIterative(vector < int > & A, int start, int end) {
stack < int > startIndex;
stack < int > endIndex;
startIndex.push(start); // save start of original array
endIndex.push(end); // save end of original array
int pivot;
while (startIndex.size() > 0) {
start = startIndex.top(); // get the start index of subarray
end = endIndex.top(); // get the end index of subarray
startIndex.pop();
endIndex.pop();
pivot = (start + end) / 2;
adjust(A, start, end, pivot); // adjust around pivot
if (pivot - 1 - start > 0) {
// indices of left subarray
startIndex.push(start);
endIndex.push(pivot - 1);
}
if (end - pivot - 1 > 0) {
// indices of right subarray
startIndex.push(pivot + 1);
endIndex.push(end);
}
// uncomment the line below to understand whats going on
// cout << start << " " << end << " " << pivot << "\n";
}
}
// main function to call
void quickSort(vector < int > & A) {
quickSortIterative(A, 0, A.size() - 1);
}
int main() {
vector<int> vect{7, 6, 0, -4, 3};
quickSort(vect);
}
```
```java
import java.util.Stack;
public class Main {
public static void exchange(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void adjust(int[] A, int start, int end, int pivot) {
int a = start, b = end;
boolean 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;
}
}
}
public static void quickSortIterative(int[] A, int start, int end) {
Stack<Integer> startIndex = new Stack<>();
Stack<Integer> endIndex = new Stack<>();
startIndex.push(start);
endIndex.push(end);
int pivot;
while (!startIndex.isEmpty()) {
start = startIndex.pop();
end = endIndex.pop();
pivot = (start + end) / 2;
adjust(A, start, end, pivot);
if (pivot - 1 - start > 0) {
startIndex.push(start);
endIndex.push(pivot - 1);
}
if (end - pivot - 1 > 0) {
startIndex.push(pivot + 1);
endIndex.push(end);
}
}
}
public static void quickSort(int[] A) {
quickSortIterative(A, 0, A.length - 1);
}
public static void main(String[] args) {
int[] vect = {7, 6, 0, -4, 3};
quickSort(vect);
}
}
```
```javascript
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 = [];
startIndex.push(start);
endIndex.push(end);
let pivot;
while (startIndex.length > 0) {
start = startIndex.pop();
end = endIndex.pop();
pivot = Math.floor((start + end) / 2);
adjust(A, start, end, pivot);
if (pivot - 1 - start > 0) {
startIndex.push(start);
endIndex.push(pivot - 1);
}
if (end - pivot - 1 > 0) {
startIndex.push(pivot + 1);
endIndex.push(end);
}
}
}
function quickSort(A) {
quickSortIterative(A, 0, A.length - 1);
}
let vect = [7, 6, 0, -4, 3];
quickSort(vect);
console.log(vect);
```
```python
def exchange(a, i, j):
temp = a[i]
a[i] = a[j]
a[j] = temp
def adjust(A, start, end, pivot):
a, b = start, end
stop = False
while not stop:
while a < pivot and A[a] <= A[pivot]:
a += 1
while b > pivot and A[b] >= A[pivot]:
b -= 1
if a >= pivot and b <= pivot:
stop = True
else:
exchange(A, a, b)
if a == pivot:
pivot = b
elif b == pivot:
pivot = a
def quickSortIterative(A, start, end):
startIndex = []
endIndex = []
startIndex.append(start)
endIndex.append(end)
pivot = 0
while startIndex:
start = startIndex.pop()
end = endIndex.pop()
pivot = (start + end) // 2
adjust(A, start, end, pivot)
if pivot - 1 - start > 0:
startIndex.append(start)
endIndex.append(pivot - 1)
if end - pivot - 1 > 0:
startIndex.append(pivot + 1)
endIndex.append(end)
def quickSort(A):
quickSortIterative(A, 0, len(A) - 1)
vect = [7, 6, 0, -4, 3]
quickSort(vect)
print(vect)
```
```csharp
using System;
using System.Collections.Generic;
class Program {
public static void Exchange(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void Adjust(int[] A, int start, int end, ref int pivot) {
int a = start, b = end;
bool 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;
}
}
}
public static void QuickSortIterative(int[] A, int start, int end) {
Stack<int> startIndex = new Stack<int>();
Stack<int> endIndex = new Stack<int>();
startIndex.Push(start);
endIndex.Push(end);
int pivot;
while (startIndex.Count > 0) {
start = startIndex.Pop();
end = endIndex.Pop();
pivot = (start + end) / 2;
adjust(A, start, end, ref pivot);
if (pivot - 1 - start > 0) {
startIndex.Push(start);
endIndex.Push(pivot - 1);
}
if (end - pivot - 1 > 0) {
startIndex.Push(pivot + 1);
endIndex.Push(end);
}
}
}
public static void QuickSort(int[] A) {
QuickSortIterative(A, 0, A.Length - 1);
}
public static void Main(string[] args) {
int[] vect = {7, 6, 0, -4, 3};
QuickSort(vect);
Console.WriteLine(string.Join(", ", vect));
}
}
```
```go
package main
import (
"fmt"
)
func exchange(a []int, i, j int) {
temp := a[i]
a[i] = a[j]
a[j] = temp
}
func adjust(A []int, start, end int, pivot *int) {
a, b := start, end
stop := false
for !stop {
for a < *pivot && A[a] <= A[*pivot] {
a++
}
for 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
}
}
}
}
func quickSortIterative(A []int, start, end int) {
startIndex := []int{}
endIndex := []int{}
startIndex = append(startIndex, start)
endIndex = append(endIndex, end)
var pivot int
for len(startIndex) > 0 {
start = startIndex[len(startIndex)-1]
end = endIndex[len(endIndex)-1]
startIndex = startIndex[:len(startIndex)-1]
endIndex = endIndex[:len(endIndex)-1]
pivot = (start + end) / 2
adjust(A, start, end, &pivot)
if pivot-1-start > 0 {
startIndex = append(startIndex, start)
endIndex = append(endIndex, pivot-1)
}
if end-pivot-1 > 0 {
startIndex = append(startIndex, pivot+1)
endIndex = append(endIndex, end)
}
}
}
func quickSort(A []int) {
quickSortIterative(A, 0, len(A)-1)
}
func main() {
vect := []int{7, 6, 0, -4, 3}
quickSort(vect)
fmt.Println(vect)
}
```Where Subarrays Wait
Recursive quick sort gets a waiting list for free: the system call stack remembers each unfinished subarray.
The iterative version must make that waiting list explicit by pushing and popping (start, end) ranges.
Where Subproblems Wait
Quick sort keeps creating smaller subarray problems after each partition.
The recursive version lets the system activation stack remember those pending ranges. The iterative version must store the same ranges manually, usually as start / end index pairs on a stack.
Iteration Or Recursion For Quick Sort?
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
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
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.
```cpp
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 HanoiFigure Below Shows The Recursion Tree For A 3 Disk Problem
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.
```cpp
#include <iostream>
void shift(char shelf1, char shelf2) {
cout << "Shift from " << shelf1 << " to " << shelf2 << "\n";
}
void Hanoi(int N, char source, char destination, char 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');
```
```java
public class Main {
public static void shift(char shelf1, char shelf2) {
System.out.println("Shift from " + shelf1 + " to " + shelf2);
}
public static void Hanoi(int N, char source, char destination, char intermediate) {
// base case
if (N == 0)
return;
// recursive case
Hanoi(N - 1, source, intermediate, destination);
shift(source, destination);
Hanoi(N - 1, intermediate, destination, source);
}
public static void main(String[] args) {
// example call for the illustrated problem
Hanoi(3, 'A', 'B', 'C');
}
}
```
```javascript
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');
```
```python
def shift(shelf1, shelf2):
print("Shift from", shelf1, "to", shelf2)
def 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')
```
```csharp
using System;
class Program {
public static void Shift(char shelf1, char shelf2) {
Console.WriteLine("Shift from " + shelf1 + " to " + shelf2);
}
public static void Hanoi(int N, char source, char destination, char intermediate) {
// base case
if (N == 0)
return;
// recursive case
Hanoi(N - 1, source, intermediate, destination);
Shift(source, destination);
Hanoi(N - 1, intermediate, destination, source);
}
public static void Main(string[] args) {
// example call for the illustrated problem
Hanoi(3, 'A', 'B', 'C');
}
}
```
```go
package main
import "fmt"
func shift(shelf1, shelf2 rune) {
fmt.Printf("Shift from %c to %c\n", shelf1, shelf2)
}
func Hanoi(N int, source, destination, intermediate rune) {
// base case
if N == 0 {
return
}
// recursive case
Hanoi(N-1, source, intermediate, destination)
shift(source, destination)
Hanoi(N-1, intermediate, destination, source)
}
func main() {
// example call for the illustrated problem
Hanoi(3, 'A', 'B', 'C')
}
```Iterative Code For Towers Of Hanoi
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.
```cpp
#include <iostream>
#include <stack>
class HanoiIterative {
stack < char > sourceStack;
stack < char > destinationStack;
stack < char > intermediateStack;
stack < int > NStack;
void shift(char shelf1, char shelf2) {
cout << "Shift from " << shelf1 << " to " << shelf2 << "\n";
}
void pushStacks(char s, char d, char i, int n) {
sourceStack.push(s);
destinationStack.push(d);
intermediateStack.push(i);
NStack.push(n);
}
void popStacks(char & s, char & d, char & i, int & n) {
// store the top of all stacks
s = sourceStack.top();
d = destinationStack.top();
i = intermediateStack.top();
n = NStack.top();
// pop one item from all stacks
sourceStack.pop();
destinationStack.pop();
intermediateStack.pop();
NStack.pop();
}
public:
void solve(int N, char source, char destination, char intermediate) {
int temp;
if (N <= 0)
return;
// temporary variables
char s = source;
char d = destination;
char i = intermediate;
int n = N;
// initialize all stacks
pushStacks(source, destination, intermediate, N);
while (!NStack.empty()) {
popStacks(s, d, i, n);
if (n == 1)
shift(s, d);
else {
// corresponds to step 3 of recursive case
pushStacks(i, d, s, n - 1);
// corresponds to step 2 of recursive case
pushStacks(s, d, i, 1);
// corresponds to step 1 of recursive case
pushStacks(s, i, d, n - 1);
}
// uncomment below to understand what is going on
// cout << s << d << i << n << "\n";
}
}
};
// example call:
// HanoiIterative h;
// h.solve(3,'A','B','C');
```
```java
import java.util.Stack;
class HanoiIterative {
Stack<Character> sourceStack = new Stack<>();
Stack<Character> destinationStack = new Stack<>();
Stack<Character> intermediateStack = new Stack<>();
Stack<Integer> NStack = new Stack<>();
void shift(char shelf1, char shelf2) {
System.out.println("Shift from " + shelf1 + " to " + shelf2);
}
void pushStacks(char s, char d, char i, int n) {
sourceStack.push(s);
destinationStack.push(d);
intermediateStack.push(i);
NStack.push(n);
}
void popStacks() {
// pop one item from all stacks
sourceStack.pop();
destinationStack.pop();
intermediateStack.pop();
NStack.pop();
}
public void solve(int N, char source, char destination, char intermediate) {
if (N <= 0)
return;
char s = source;
char d = destination;
char i = intermediate;
int n = N;
pushStacks(source, destination, intermediate, N);
while (!NStack.empty()) {
s = sourceStack.peek();
d = destinationStack.peek();
i = intermediateStack.peek();
n = NStack.peek();
popStacks();
if (n == 1) {
shift(s, d);
} else {
pushStacks(i, d, s, n - 1);
pushStacks(s, d, i, 1);
pushStacks(s, i, d, n - 1);
}
}
}
public static void main(String[] args) {
HanoiIterative h = new HanoiIterative();
h.solve(3, 'A', 'B', 'C');
}
}
```
```javascript
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 = source;
let d = destination;
let i = intermediate;
let n = N;
this.pushStacks(source, destination, intermediate, N);
while (this.NStack.length > 0) {
s = this.sourceStack[this.sourceStack.length - 1];
d = this.destinationStack[this.destinationStack.length - 1];
i = this.intermediateStack[this.intermediateStack.length - 1];
n = this.NStack[this.NStack.length - 1];
this.popStacks();
if (n === 1) {
this.shift(s, d);
} else {
this.pushStacks(i, d, s, n - 1);
this.pushStacks(s, d, i, 1);
this.pushStacks(s, i, d, n - 1);
}
}
}
}
// example call:
const h = new HanoiIterative();
h.solve(3, 'A', 'B', 'C');
```
```python
class HanoiIterative:
def __init__(self):
self.sourceStack = []
self.destinationStack = []
self.intermediateStack = []
self.NStack = []
def shift(self, shelf1, shelf2):
print("Shift from", shelf1, "to", shelf2)
def pushStacks(self, s, d, i, n):
self.sourceStack.append(s)
self.destinationStack.append(d)
self.intermediateStack.append(i)
self.NStack.append(n)
def popStacks(self):
self.sourceStack.pop()
self.destinationStack.pop()
self.intermediateStack.pop()
self.NStack.pop()
def solve(self, N, source, destination, intermediate):
if N <= 0:
return
s = source
d = destination
i = intermediate
n = N
self.pushStacks(source, destination, intermediate, N)
while self.NStack:
s = self.sourceStack[-1]
d = self.destinationStack[-1]
i = self.intermediateStack[-1]
n = self.NStack[-1]
self.popStacks()
if n == 1:
self.shift(s, d)
else:
self.pushStacks(i, d, s, n - 1)
self.pushStacks(s, d, i, 1)
self.pushStacks(s, i, d, n - 1)
# example call:
h = HanoiIterative()
h.solve(3, 'A', 'B', 'C')
```
```csharp
using System;
using System.Collections.Generic;
class HanoiIterative {
Stack<char> sourceStack = new Stack<char>();
Stack<char> destinationStack = new Stack<char>();
Stack<char> intermediateStack = new Stack<char>();
Stack<int> NStack = new Stack<int>();
void Shift(char shelf1, char shelf2) {
Console.WriteLine("Shift from " + shelf1 + " to " + shelf2);
}
void PushStacks(char s, char d, char i, int n) {
sourceStack.Push(s);
destinationStack.Push(d);
intermediateStack.Push(i);
NStack.Push(n);
}
void PopStacks() {
sourceStack.Pop();
destinationStack.Pop();
intermediateStack.Pop();
NStack.Pop();
}
public void Solve(int N, char source, char destination, char intermediate) {
if (N <= 0)
return;
char s = source;
char d = destination;
char i = intermediate;
int n = N;
PushStacks(source, destination, intermediate, N);
while (NStack.Count > 0) {
s = sourceStack.Peek();
d = destinationStack.Peek();
i = intermediateStack.Peek();
n = NStack.Peek();
PopStacks();
if (n == 1) {
Shift(s, d);
} else {
PushStacks(i, d, s, n - 1);
PushStacks(s, d, i, 1);
PushStacks(s, i, d, n - 1);
}
}
}
public static void Main(string[] args) {
HanoiIterative h = new HanoiIterative();
h.Solve(3, 'A', 'B', 'C');
}
}
```
```go
package main
import (
"fmt"
)
type HanoiIterative struct {
sourceStack []rune
destinationStack []rune
intermediateStack []rune
NStack []int
}
func (h *HanoiIterative) shift(shelf1, shelf2 rune) {
fmt.Printf("Shift from %c to %c\n", shelf1, shelf2)
}
func (h *HanoiIterative) pushStacks(s, d, i rune, n int) {
h.sourceStack = append(h.sourceStack, s)
h.destinationStack = append(h.destinationStack, d)
h.intermediateStack = append(h.intermediateStack, i)
h.NStack = append(h.NStack, n)
}
func (h *HanoiIterative) popStacks() {
h.sourceStack = h.sourceStack[:len(h.sourceStack)-1]
h.destinationStack = h.destinationStack[:len(h.destinationStack)-1]
h.intermediateStack = h.intermediateStack[:len(h.intermediateStack)-1]
h.NStack = h.NStack[:len(h.NStack)-1]
}
func (h *HanoiIterative) Solve(N int, source, destination, intermediate rune) {
if N <= 0 {
return
}
s := source
d := destination
i := intermediate
n := N
h.pushStacks(source, destination, intermediate, N)
for len(h.NStack) > 0 {
s = h.sourceStack[len(h.sourceStack)-1]
d = h.destinationStack[len(h.destinationStack)-1]
i = h.intermediateStack[len(h.intermediateStack)-1]
n = h.NStack[len(h.NStack)-1]
h.popStacks()
if n == 1 {
h.shift(s, d)
} else {
h.pushStacks(i, d, s, n-1)
h.pushStacks(s, d, i, 1)
h.pushStacks(s, i, d, n-1)
}
}
}
func main() {
h := HanoiIterative{}
h.Solve(3, 'A', 'B', 'C')
}
```Fill In
How many recursive calls will be required to check if the number 37 is prime using recursion?
Take Away Lesson
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 LISPhave 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.
Order Sequence
How would you replace recursion with iteration? Select the correct order.
One Pager Cheat Sheet
One Pager Cheat Sheet
- Both iteration and
recursioncan 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
repetitionof a block of code usingcontrol variablesor 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
printListfunction which uses thedivide and conquerprinciple to print the numbers1to5. - - Iteration reuses one control flow; recursion builds a chain of smaller function calls.
- - Iteration updates state in one loop; recursion stores state across multiple function calls.
- The
printListfunction implementsrecursionby 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 casewill not raise an exception, but can lead tostack overflowif the maximum number of recursive calls is exceeded. - Recursion is a technique that enables a function to save its
local variablesandparameterson anactivation stack, which is thenpopped offwhen the function exits or thebase caseis reached. - The
printListfunction 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
iterativeorrecursiveimplementation in C++. - - Code before the recursive call runs on the way down; code after it runs on the way back up.
- - Recursive calls descend to a base case, then return upward to finish the pending work.
- The
iterativesolution is more efficient for programming languages such asC++orJavaas it runs in constant memory, compared to therecursivesolutions which generates 4 records on theactivation stackfor each call. - The recursive version of the factorial function takes up more
memorydue to increasedactivation stackrecords, while being less optimal in languages likeC++andJava. - Quick Sort is a naturally
recursivesorting algorithm that divides the entire array into smaller pieces, and is conceptually easier to implement via recursion. - The clear concept behind
Quick Sortis easily understood from the elegant and simple recursive version of the algorithm, which adjusts elements around a pivot before callingquickSortrecursively on both subarrays. - We need to
implement our own stackto maintain theindicesof the left and right subarrays for the iterative version ofquickSort. - - Recursive quick sort uses the call stack; iterative quick sort stores pending subarray ranges manually.
- - Recursive quick sort and iterative quick sort do the same partition work; they differ in where pending subarrays are stored.
- Of course, the main question now is: which solution to go for,
iterativeorrecursive, and I would still advise you to go for theiterativesolution to avoid segmentation faults while therecursiveversion is easier to write and understand. - The
Towers of Hanoigame 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 Hanoiproblem 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 caseand 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.