Basic Recursions with C
Review of basic recursions. This part is more conceptual than the previous sections.
Shortcut for Quick Review:
Update (2020.12.05): Fix stack size in answer code (Replace Recursion with Loops)
Steps for Writing Recursion Code
Recursion in programming is like induction in mathematics. So, if you have trouble understanding recursion, maybe you can start by reviewing the concept of mathematical induction.
Every good recursion code writing consists of four parts or steps. The first step is called “The Goal”. The programmer defines a function prototype that can solve the problem once implemented correctly. But of course… the function isn’t implemented yet. The second step is called “The Basic Case”. The programmer solves the simplest case to ensure the termination of recursion calls in later steps. The third step is called “The Inductive Case”. The programmer solves other complicated cases by breaking it down to simpler cases that utilize the defined function as if it is already fully implemented. This takes the ordinary basic case and uses it to do something extraordinary. The code works now, but, the programmer doesn’t have an intuition on why it works yet. He or she should think over the code and convince himself or herself why the code works. That’s why every recursion code writing should have the fourth step, the most important but so easily forgotten part, the part we call “The Intuition”.
– Imitation Quote Christopher Priest in The Prestige
Steps  Recursion  Induction 

The Goal  What does the function do  $f(n)$ have some certain properties 
The Basic Case  if (n == 1) return ...; 
prove $f(1)$ satisfies the properties 
The Inductive Case  else func(n1); return ...; 
prove $f(n)$ satisfies the properties, by assuming $f(k)$ works $\forall k \in [1,n1]$ 
The Intuition  Rethink the intuition  on why it works 
Let’s take the classic Tower of Hanoi as an example.
Tower of Hanoi
The objective of the puzzle is to move the entire stack from rod1 to rod3, obeying the following simple rules:
 Only one disk can be moved at a time.
 Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
 No larger disk may be placed on top of a smaller disk.
Now, we want to output the solution in text format, let’s follow the 4 steps.

“The Goal”: Define a function prototype that can solve the problem once implemented correctly.
Define the function prototype and what does it do.
Click to expand Answer
✔️ Answer
void move_hanoi(int n, int from, int to, int temp);
This function moves $n$ disks on the top of the
from
rod to theto
rod legally. (without violating the rules) Thetemp
rod only has disks that are larger than the top $n$ disks, so it can be used to temporarily store disks as if the rod is empty. We assume this function is implemented correctly. So if the problem is to move 3 disks from rod1 to rod3, we can achieve it by a single function call,move_hanoi(3, 1, 3, 2)
This part should be the hardest part since the function definition may be tricky to define. Sometimes we even need to think about how to deal with the induction / recursive case and then we can think of this function definition.

“The Basic Case”: Solve the simplest case to ensure the termination of recursion calls in later steps.
Assume that we are only required to move a single disk, how should we move it.
Click to expand Answer
✔️ Answer
// Move the disk directly to the target rod. printf("Move disk %d from %d to %d\n", 1, from, to);
If we have only one disk, any move is legal.
Once this basic case is implemented, we can use it without worrying about infinite recursion.

“The Inductive Case”: Solve other complicated cases by breaking it down to simpler cases that utilize the defined function as if it is already fully implemented.
Since the basic case is implemented, we now assume that
move_hanoi(1, ...)
,move_hanoi(2, ...)
,move_hanoi(n1, ...)
are all implemented. Now we can use them to move the $n$ disks. It’s similar to strong mathematical induction here.Keep in mind that we can use
move_hanoi
for $[1,n1]$ as if it’s already implemented. You can use it freely likeprintf
orstrlen
, without worrying that the function isn’t fully implemented yet.The importance of this thought is ofter underrated. Some students may think: “I haven’t implemented this function yet, why can I call it?”, then they start writing codes that can be done by a simple recursion function call. By doing so, they’ll eventually find out that they need to write infinite lines of code if they do not utilize the recursion function call.
If you know mathematical induction, you can write the code like writing mathematical proofs. As long as the recursion function calls only use $f(k)$, $\forall k\in [1,n1]$, the call will be correct.
Recall the definition of the function.
void move_hanoi(int n, int from, int to, int temp);
This function moves $n$ disks on the top of the
from
rod to theto
rod legally. (without violating the rules) Thetemp
rod only has disks that are larger than the top $n$ disks, so it can be used to temporarily store disks as if the rod is empty.And now, for the inductive/recursive case:
Click to expand Answer
✔️ Answer
// Keep the largest disk below and move the upper disks to the temporary rod. move_hanoi(n  1, from, temp, to); // Move the largest disk to the target destination. printf("Move disk %d from %d to %d\n", n, from, to); // Stack the upper disks above the largest disk. move_hanoi(n  1, temp, to, from);
The
temp
rod may not be empty, but we can still temporarily store disks on it since the disks on it are larger than the disks that we’re currently moving. 
“The Intuition”: The code works now, but, the programmer doesn’t understand why it actually works yet. He or she should think over the code and convince himself or herself why the code works.
Explain the entire code to yourself and convince yourself of its correctness.
Click to expand Answer
✔️ Answer
// This function moves $n$ disks on the top of the `from` rod to the `to` rod legally. (without violating the rules) The `temp` rod only has disks that are larger than the top $n$ disks, so it can be used to temporarily store disks as if the rod is empty. void move_hanoi(int n, int from, int to, int temp); void move_hanoi(int n, int from, int to, int temp) { if (n == 1) // If there are only one disk to move, // Move the disk directly to the target rod. printf("Move disk %d from %d to %d\n", 1, from, to); else { // If there are multiple disks to move, // Keep the largest disk below and move the upper disks to the temporary rod. move_hanoi(n  1, from, temp, to); // Move the largest disk to the target destination. printf("Move disk %d from %d to %d\n", n, from, to); // Stack the upper disks above the largest disk. move_hanoi(n  1, temp, to, from); } }
Think over the entire process and find out that the code we write is equivalent to proving the correctness through mathematical induction.

Bonus Section: Time Complexity Analysis
Analyze how many movements occur.
Click to expand Answer
✔️ Answer
Assume we have $n$ disks, and each move requires $c$ time.
\[\begin{align} T(0) &= 0 \\\\ T(1) &= c \\\\ T(n) &= 2\cdot T(n1)+c \\\\ &= 2\cdot 2\cdot T(n2)+2\cdot c+c \\\\ &= 2\cdot 2\cdot 2\cdot T(n3)+4\cdot c+2\cdot c+c \\\\ &= 2^n \cdot T(0) + \sum_{k=0}^{n1}(2^k\cdot c) \\\\ &= c\cdot \sum^{n1}_{k=0}2^k \end{align}\]Sum of geometric sequence:
\[\sum^{n1}_{k=0}2^k=\frac{2^0 \cdot (12^{n1})}{12}=2^n1\] \[T(n)=(2^n1)\cdot c\]We proved that the time complexity is $O(2^n)$, total $2^n1$ moves. This part is a bonus section, you’ll learn more about it in the Design and Analysis of Algorithm course.
Here’s a nice image from Wikipedia.
The leftmost column is “The Goal”. It defines the function and uses it as a black box, we only need to know what it does, without knowing how it does it.
The second column (counting from left) is “The Recursion Case”. It uses the function as if it is implemented, but only use $f(k)$, $\forall k\in [1,n1]$. (Does not use $f(n)$)
The bottomright part is “The Basic Case”, we can just move the disk directly.
For other parts, it enumerates each move. It is almost impossible to enumerate this in our head for a large enough $n$. So we can use recursion to abstract this part and prove its correctness.
There are many other solutions that can solve the Tower of Hanoi problem, feel free to come up with other solutions on your own. The solution shown here is the simplest and straightforward one in my opinion.
Variable Scopes and Function Call Stack
Note that all variables in each recursive function call are a new local variable with its own scope.
For the first move in a $n=3$ Tower of Hanoi problem, we can visualize the call stack of the first call to basic case as below.
move_hanoi(3, 1, 3, 2);
void move_hanoi_depth1(int n1=3, int from1=1, int to1=3, int temp1=2) {
move_hanoi_depth(n1  1, from1, temp1, to1);
// The call above is shown as 'move_hanoi_depth2` below.
printf("Move disk %d from %d to %d\n", n1, from1, to1);
move_hanoi_depth(n1  1, temp1, to1, from1);
}
void move_hanoi_depth2(int n2=2, int from2=1, int to2=2, int temp2=3) {
move_hanoi_depth(n2  1, from2, temp2, to2);
// The call above is shown as 'move_hanoi_depth3` below.
printf("Move disk %d from %d to %d\n", n2, from2, to2);
move_hanoi_depth(n2  1, temp2, to2, from2);
}
void move_hanoi_depth3(int n3=1, int from3=1, int to3=3, int temp3=2) {
printf("Move disk %d from %d to %d\n", 1, from3, to3);
// This function will return to 'move_hanoi_depth2' above, and continue running the subsequent codes.
}
The bottom graph is the full call/return order of the case with 3 disks.
You may observe that the $n=1$, $n=2$, $n=3$ vertices in the graph above corresponds to the movements of the green
, blue
, red
disk in the figure below, respectively.
Photo Credit: Tower of Hanoi on The Math Forum
With the knowledge of variable scopes, function stacks and mathematical induction, you should have the ability to write recursion codes for most problems.
Replace Loops with Recursion
for
loops and recursion is interchangeable. However, recursion has higher overhead due to many function calls, you’ll learn more about it in the Computer Architecture course.
The following code is the code of Selection Sort using for
loop.
#include <stdio.h>
#define MAX 10
#define swap(a, b) if (a != b) {(*a)^=(*b); (*b)^=(*a); (*a)^=(*b);}
void selection_sort(int* a, int size);
int a[MAX] = {3, 7, 9, 1, 4, 0, 8, 6, 2, 5};
int main(void) {
selection_sort(a, MAX);
for (int i = 0; i < MAX; i++) {
printf("%d ", a[i]);
}
return 0;
}
void selection_sort(int* a, int size) {
int i, j, min_idx;
// Put the ith smallest number in a[i].
for (i = 0; i < size  1; i++) {
// Scan through the remaining array and pick the smallest element.
min_idx = i;
for (j = i+1; j < size; j++) {
if (a[min_idx] > a[j])
min_idx = j;
}
// Swap the smallest number to the left.
swap(&a[i], &a[min_idx]);
}
}
Modify the code to use recursion without using any explicit loops (while
, for
).
Click to expand Answer
✔️ Answer
First, remove the outer loop.
#include <stdio.h>
#define MAX 10
#define swap(a, b) if (a != b) {(*a)^=(*b); (*b)^=(*a); (*a)^=(*b);}
void selection_sort(int* a, int size);
int a[MAX] = {3, 7, 9, 1, 4, 0, 8, 6, 2, 5};
int main(void) {
selection_sort(a, MAX);
for (int i = 0; i < MAX; i++) {
printf("%d ", a[i]);
}
return 0;
}
void selection_sort(int* a, int size) {
int j, min_idx;
if (size == 1)
// No need to sort a single number.
return;
// Scan through the remaining array and pick the smallest element.
min_idx = 0;
for (j = 1; j < size; j++) {
if (a[min_idx] > a[j])
min_idx = j;
}
// Swap the smallest number to the first.
swap(&a[0], &a[min_idx]);
// Since the first element is smallest, we can sort the remaining array recursively.
selection_sort(a+1, size1);
}
Second, remove the inner loop.
#include <stdio.h>
#define MAX 10
#define swap(a, b) if (a != b) {(*a)^=(*b); (*b)^=(*a); (*a)^=(*b);}
int get_min_idx(int* a, int size);
void selection_sort(int* a, int size);
int a[MAX] = {3, 7, 9, 1, 4, 0, 8, 6, 2, 5};
int main(void) {
selection_sort(a, MAX);
for (int i = 0; i < MAX; i++) {
printf("%d ", a[i]);
}
return 0;
}
int get_min_idx(int* a, int size) {
if (size == 1)
return 0;
int min_idx = get_min_idx(a+1, size1) + 1;
if (a[min_idx] > a[0])
return 0;
return min_idx;
}
void selection_sort(int* a, int size) {
int min_idx;
if (size == 1)
// No need to sort a single number.
return;
// Get the smallest element.
min_idx = get_min_idx(a, size);
// Swap the smallest number to the first.
swap(&a[0], &a[min_idx]);
// Since the first element is smallest, we can sort the remaining array recursively.
selection_sort(a+1, size1);
}
Replace Recursion with Loops
The following code is the Tower of Hanoi code using recursion.
#include <stdio.h>
void move_hanoi(int n, int from, int to, int temp);
int main(void) {
move_hanoi(3, 1, 3, 2);
return 0;
}
void move_hanoi(int n, int from, int to, int temp) {
if (n == 1)
// If there are only one disk to move,
// Move the disk directly to the target rod.
printf("Move disk %d from %d to %d\n", 1, from, to);
else {
// If there are multiple disks to move,
// Keep the largest disk below and move the upper disks to the temporary rod.
move_hanoi(n  1, from, temp, to);
// Move the largest disk to the target destination.
printf("Move disk %d from %d to %d\n", n, from, to);
// Stack the upper disks above the largest disk.
move_hanoi(n  1, temp, to, from);
}
}
Modify the code to use loops without recursions.
Click to expand Answer
✔️ Answer
#include <stdio.h>
#define MAX 10000
typedef struct {
int n, from, to, temp;
} Record;
Record stack[MAX];
int top = 1;
void move_hanoi(int n, int from, int to, int temp);
int main(void) {
move_hanoi(3, 1, 3, 2);
return 0;
}
void move_hanoi(int n, int from, int to, int temp) {
stack[++top] = (Record) {n, from, to, temp};
while (top != 1) {
Record record = stack[top];
if (record.n == 1  record.temp == 1) {
printf("Move disk %d from %d to %d\n", record.n, record.from, record.to);
continue;
}
stack[++top] = (Record) {record.n  1, record.temp, record.to, record.from};
stack[++top] = (Record) {record.n, record.from, record.to, 1};
stack[++top] = (Record) {record.n  1, record.from, record.temp, record.to};
}
}
Local vs. Global Variables in Recursion
For recursion functions, it’s better to only use local variables to avoid misconceptions. Only using local variables can keep your code clean and keep the structure of mathematical induction.
However, accessing global variables may make your code simpler in some cases, but use it in caution.
For the next assignment, we’ll review binary representations.
Epilogue
You can try to learn and implement NQueens, Binary Search, Merge Sort, Quick Sort, etc by yourself, following the 4 main steps mentioned above. The concept of recursion not only needs a lot of practice but also requires some critical thinking. After your code got AC, it’s better to think your code all over again and review how it works exactly.
Photo Credit: Screenshot of Google Search page.
Comments