Recursion

Many problems can be solved with repetition by self-reference:

Baize In the Republic of Palau, there's a semi-government agency called PPUC (Palau Public Utilities Corporation). This monolithic entity is the single electricity, water, and sewage provider for the entire nation. Our friend Brak recently bought a house and wants to open a utilities account. He fills the application and submits it to a representative.

The representative says, "Oh, this is a new account. I can't sign off on it unless the clerk signs it." The representative hands it to the clerk.

The clerk says "Oh, this is a new account. I can't sight off on it unless the manager signs it." The clerk hands it to the manager.

The manager says, "Oh, this is a new account. I can't sign off on it unless the director signs it." The manager hands it to the director.

The director says, "Oh, a new account. Looks good. Signed."

The signed form goes back to the manager. "Director signed off. Sign."

The signed form goes back to the clerk. "Manager signed off. Signed."

The signed form goes back to the representative. "Clerk signed off. Signed. You'll have utilities by end of day."

Cleaver Our friend Brak has a daughter, Kukau. After finishing her homework, Kukau wants to know if all her answers are correct before she submits her assignment.

She goes to her teacher, Dort, and asks her, "Sensei, I want to know if all my answers on this list are correct. The list is ${[1, 4, 9, 3].}$ "

Dort replies, "I can only check if the first answer in the list is incorrect."

Kukau thinks for a moment, then asks, "Ok. How about this list ${[1, 4, 9, 3]?}$ "

Dort replies, "The first answer in that list is not incorrect."

Kukau then asks, "Now how about this list ${[4, 9, 3]?}$ "

Dort again replies, "The first answer in that list is not incorrect."

Now excited, "And how about this one ${[9, 3]?}$ "

Once more, "The first answer in that list is not incorrect."

Smirking, "And this one ${[3]?}$ " "The first answer in that list is not incorrect." Amused, Kukau asks, "[]?"

"That is the empty list. There can be no incorrect answer because there's nothing there."

Gleefully, Kukau exlaims, "Aha, so my answers are all correct!"

Recursion is the programming technique of solving a problem whose solution depends on solutions to smaller instances of the same problem. This is done by calling a function that calls itself from within itself. To understand how this works, it's worth recalling the control flow with function calls. Say we executed this code:

#include <iostream>

void func(int n) {
	int x = n * n;
	std::cout << x << std::endl;
}

int main() {
	int a = 2;
	int b = 3;
	std::cout << a << std::endl;
	func(a);
	std::cout << b << std::endl;
	return 0;
}

In the code above, we can trace control in the program as such:

	main()
	|
	int a = 2;
	|
	int b = 3;
	|
	std::cout &lt;&lt; a &lt;&lt; std::endl;
	|
	func(a);--------+
									|
								int n = a;
								int x = n * n;
								std::cout &lt;&lt; x &lt;&lt; std::endl;
									|
	main()----------+
	|
	std::cout &lt;&lt; a &lt;&lt; std::endl;
	|
	return 0;

In the diagram above, main() executes as expected, but once it encounters func(a), control transfers to func(a). Then, once func(a) has finished its computation, control returns to main().

Writing recursive functions is essentially writing instructions for the journey from (a) the call to the recursive function to (b) a known fact about the problem. Keeping this perspective in mind, whenever we write recursive functions, there are three key rules to follow: (1) We must state when to stop the journey. (2) We must state how to take one step in the journey. (3) We must know how to break the journey down into a single step plus a smaller journey.

The point where we stop (i.e., a known fact about the problem), is called the base case. We must always have this base case, lest we embark on an infinite journey. When we state how to take one step in the journey, we are simply moving along the journey. When we break the journey down into a single step plus a smaller journey, we are performing induction.

All this said, let's consider an example:

#include <iostream>

void f(int n, int& count) {
	if (n > 0) {
		std::cout<<"run before f(n: "<< n <<", count: "<< count <<")\n";
		count++;
		f(n - 1, count);
	} else {
		std::cout << "end\n";
	}
}

int main() {
	int i = 0;
	f(4, i);
	return 0;
}

run before f(n: 4, count: 0)
run before f(n: 3, count: 1)
run before f(n: 2, count: 2)
run before f(n: 1, count: 3)
end

Inside main(), we called f(4, i), where i = 0. This transfers control to f(). In f(), we have a condition, n > 0. If this condition is true, we execute the following statements: (1) output a statement, (2) increment count (which is initially 0); and (3) call f(n-1, count). If the condition is false, output end. Reasoning through this process, the program's output is as expected. We can visualize the flow as such (assume we just printed the value of n):

	func(4, 0)
		/  \
	4   func(3, 1)
				/  \
			3   func(2, 2)
						/  \
					2   func(1, 3)
								/  \
							1   func(0, 4)
										|
										end

Let's see what happens when we move the console output line to after the recursive call:

#include <iostream>

void f(int n, int& count) {
	if (n > 0) {
		count++;
		f(n - 1, count);
		std::cout<<"run after f(n: " << n <<", count: " << count << ")\n";
	} else {
		std::cout << "end\n";
	}
}

int main() {
	int i = 0;
	f(4, i);
	return 0;
}

end
run after f(n: 1, count: 4)
run after f(n: 2, count: 4)
run after f(n: 3, count: 4)
run after f(n: 4, count: 4)

Interesting, notice how it outputs end first. Why is this output different? Well, notice that the output value of count is 4 rather than the incrementing we saw earlier. This is because when we run f(), it never actually finishes executing until we get to f(0, 4). At that point, we run the else-block, "end". Additionally at that point, count has incremented to 4. As such, when f(0, 4) has finished executing, f(1, 4) is exeuted, then f(2, 4), and so on, all way back up to f(4, 4). Visually:

	f(4, 0)
			\
			f(3, 1)
				\
				f(2, 2)
					\
					f(1, 3)
						\
						f(0, 4)
							|
							print end
						/
				f(1,3) &amp;rarr; print f(1,4)
					/
			f(2,2) &amp;rarr; print f(2,4)
				/
		f(3,1) &amp;rarr; print f(3,4)
			/
	f(4,0) &amp;rarr; print f(4,4)

The above is an example of a classical recursion or simple recursion. It's the kind of recursion most commonly used in programming. There are, however, other types of recursion: tail recursion, head recursion, tree recursion, mutual recursion, and nested recursion. We will explore each type in turn.

Recursion & Memory

Unlike loops, the system stack will provide separate areas of memory for each recursive call. For example, consider this recursive function for summing the elements of an array:

#include <iostream>

int summate(int array[], int arrayLength) {
	if (arrayLength == 1) {
		return array[0];
	} else {
		int sum = summate(array, arrayLength - 1);
		return sum + array[arrayLength - 1];
	}
}

int main() {
	int list[4] = {1, 0, 3, 2};
	int listSum = summate(list, 4);
	std::cout << listSum << std::endl;
	return 0;
}

Each time we call summate(), we create a new stack, where each local variable and argument of the recursive call is isolated from the other recursive call stacks. In this case, there four stacks total: summate(list, 4), summate(list, 3), summate(list, 2), and summate(list, 1).

	main()
	===================================
	[ int list = {1, 0, 3, 2};        ]
	[ int listSum = summate(list, 4); ]
	===================================
									|
									|
									summate(list, 4)
									===============================
									[ int array = {1, 0, 3, 2};   ]
									[ int arrayLength = 4;        ]
									[ int sum = summate(list, 3); ]
									===============================
															|
															|
															summate(list, 3)
															===============================
															[ int array = {1, 0, 3, 2};   ]
															[ int arrayLength = 3;        ]
															[ int sum = summate(list, 2); ]
															===============================
																					|
																					|
																					summate(list, 2)
																					==============================
																					[ int array = {1, 0, 3, 2};  ]
																					[ int arrayLength = 2;       ]
																					[ int sum = summate(list, 1);]
																					==============================
																											|
																											|
																											summate(list, 1)
																											==============================
																											[ int array = {1, 0, 3, 2};  ]
																											[ int arrayLength = 1;       ]
																											{ return 1                   }
																											==============================
																											|
																											|
																				summate(list, 2)
																				~~~~~~~~~~~~~~~~
																				{ return 1 + 0 }
																				~~~~~~~~~~~~~~~~
																				|
																				|
													summate(list, 3)
													~~~~~~~~~~~~~~~~
													{ return 1 + 3 }
													~~~~~~~~~~~~~~~~
													|
													|
						summate(list, 4)
						~~~~~~~~~~~~~~~~
						{ return 4 + 2 }
						~~~~~~~~~~~~~~~~
						|
						|
				main()
				~~~~~~~~~~~~~~~~~~~~
				[ int list sum = 6 ]
				~~~~~~~~~~~~~~~~~~~~

Time Complexity of Classical Recursion

Consider this linear-recursive approach to the factorial function:

#include <iostream>

int factorial(int n) {
	if (n == 0) {
		return 1;
	} else {
		return n * factorial(n - 1);
	}
}

int main() {
	int a = 4;
	int b = factorial(a);
	std::cout << a << "! = " << b << std::endl;
	return 0;
}

4! = 24

What is the time complexity for this function? Well, each call to factorial() results in several computational steps: (1) Checking whether n == 0, (2) If n != 0, executing n times the result of factorial(n - 1); (3) the evaluation of n - 1. We can think of this roughly as ${3n,}$ where ${n}$ is the number of calls to factorial() (which corresponds to argument for n). Accordingly, we say that the linear recursion function above has a time complexity of O(n). This is linear time.

Alternatively, we can determine the time complexity of factorial() with a recurrence relation. To do so, we first recognize that there are two discrete cases for factorial()'s evaluation. If n == 0, we perform a single step, return 1. If n != 0 (i.e., n > 0), we perform the computational step n * factorial(n - 1). Next, whenever we call factorial(), we have roughly 3 separate computations: Checking if n == 0, multiplying n, and evaluating n - 1. Thus, we can express factorial(n - 1) as the relation ${T(n - 1).}$ Accordingly, we can express factorial(n) as the relation ${T(n) = T(n - 1)}$ It follows then that:

T(n) = \begin{cases} 1 &n = 0 \\ T(n-1) + 3 &n > 0 \end{cases}

From this recurrence relation, we can then compute the time complexity. Since ${T(n) = T(n - 1) + 3,}$ it follows that ${T(n - 1) = T(n - 2) + 3.}$ As such, ${T(n) = T(n - 2) + 3 + 3 = T(n) = T(n - 2) + 6.}$ If we continued this substitution ${k}$ times, we would have ${T(n) = T(n - k) + 2k.}$ Now, if we assume that ${n - k = 0,}$ we can infer that ${n = k.}$ And given that ${n = k,}$ we have ${T(n) = T(n - n) + 2n;}$ i.e., ${T(n) = T(0) + 2n.}$ But we that ${T(0)}$ is ${1,}$ so ${T(n) = 1 + 2n.}$ Applying complexity analysis, we have the time complexity of ${O(n).}$

Tail Recursion

The first example in the previous section was an example of tail recursion — a recursive function where the recursive call is the

last expression to be evaluated. We call this a tail call. Roughly, a tail recursive function takes the form:

fn {
	...
	`${\Delta n}`
}

For example, the previous factorial() function is not a tail recursive. This is because factorial() is not the last computation to perform. It's multiplication. To rewrite factorial() as a tail recursive function, the multiplication must occur before the tail call. We can do so by passing the result of the multiplication as a parameter:

#include <iostream>

int factorial(int n, int m = 1) {
	if (n == 0) {
		return m;
	}
	return factorial(n - 1, m * n);
}

int main() {
	int x = 5;
	int y = factorial(x);
	std::cout << "5! = " << y << std::endl;
	return 0;
}

5! = 120

Notice that with this implementation, the last line to execute is a call to factorial().

Note that every tail recursive function can be written as a loop, and every loop can be written as a tail recursive function. For example, we could have written the same function above as such:

#include <iostream>

int factorial(int n) {
	int product = 1;
	if (n == 0) {
		return product;
	} else {
		for (int i = 1; i <= n; i++) {
			product *= i;
		}
	}
	return product;
}

int main() {
	int x = 7;
	int y = factorial(x);
	std::cout << "7! = " << y << std::endl;
	return 0;
}

7! = 5040

Both these implementations work the same way. There is no difference between these two implementations, at least in terms of time complexity. Both have a time complexity of ${O(n).}$ Where they may differ is in terms of space complexity. With each call to factorial(), we generate a new stack frame. And with enough tail calls, we can run into stack overflow. Fortunately, most modern C++ compilers have implemented tail call optimization (TCO). With TCO, the compiler recognizes tail calls, and optimizes space allocation.

Head Recursion

The opposite of tail recursion is head recursion. With head recursion, the recursive call before other statements are executed. Visually:

fn {
	f(Δn);
	...
	return ...;

}

Using the factorial() example again, here is a head-recursive implementation:

#include <iostream>

	int factorial(int n, int m = 1) {
		if (n > 0) {
			return factorial(n - 1, n * m);
		} else {
			return m;
		}
	}

	int main() {
		int x = 7;
		int y = factorial(x);
		std::cout << "7! = " << y << std::endl;
		return 0;
	}

7! = 5040

As can be seen, both tail and head recursion have a time complexity of ${O(n)}$ and a space complexity of ${O(n).}$ The difference, however, is that head recursion tends to be much more difficult to implement as a loop.

Tree Recursion

All of the examples we've used above are instances of linear recursion. In linear recursion, the recursive function is defined with only one call to itself. If the recursive function is defined with either multiple calls to itself, then we have an instance of tree recursion. Roughly, this looks like the following:

f(n) {
	f(Δn);
	f(Δn);
}

Many problems are best solved with tree recursion. Consider a few examples below.

Compute the ${n^{\text{\scriptsize{th}}}}$ Fibonnaci Number

In the Fibonacci sequence, each element of the sequence is the sum of the preceding two elements: ${\lang 0, 1, 1, 2, 3, 5, 8, \ldots \rang.}$ Mathematically, this sequence is defined with the recurrence relation:

Fib(n) = \begin{cases} 0 &\textit{if } \space n = 0 \\ 1 &\textit{if } \space n = 1 \\ Fib(n - 1) + Fib(n - 2) &\textit{else} \end{cases}

This definition lends itself to tree recursion:

#include <iostream>

int fib(int n) {
	int result = 0;
	if (n == 0) { return 0; }
	else if (n == 1) { return 1; }
	else {
		result = fib(n - 1) + fib(n - 2);
	}
	return result;
}

int main() {
	int index = 6;
	int fib6 = fib(6);
	std::cout << fib6 << std::endl;
	return 0;
}

Visualizing the tree:

Number of Permutations

Suppose we played a game where we could score either a 1 point or 2 points. Given ${n}$ number of maximum points, how many possible arrangements of 1 point and 2 points are there to reach ${n?}$ Again, this problem lends itself to tree recursion. What we're really being asked to do is: How many different ways can you add 1 and 2 such that you get ${n?}$

#include <iostream>

int permute(int n) {
	int permutations;
	if (n == 1) { return 1; }
	else if (n == 2) { return 2; }
	else {
		permutations = permute(n - 1) + permute(n - 2);
	}
	return permutations;
}

int main() {
	int maxPoints = 35;
	int numberOfPossibleArrangements = permute(maxPoints);
	std::cout << numberOfPossibleArrangements << std::endl;
	return 0;
}

14930352

Complexity of Tree Recursion

Tree recursion alone does not lend itself well to time complexity. To understand the tree recursion complexity, let's consider a simple example:

#include <iostream>

void fun(int n) {
	if (n > 0) {
		std::cout << "fun(" << n << ")" << std::endl;
		fun(n - 1);
		fun(n - 1);
	}
}

int main() {
	int n = 3;
	fun(3);
	return 0;
}

fun(3)
fun(2)
fun(1)
fun(1)
fun(2)
fun(1)
fun(1)

Let's parse how fun(3) is executed. First, fun(3) results in the console output fun(3), as expected. Then, there is the call to fun(n - 1), which is fun(2). Then, when fun(2) is executed, we output to the console, and call fun(1) and fun(1) again. Only after fun(2) has finished executing do we get to the fun(1) from fun(3). Visualizing these calls, we see a tree:

For each call, once we reach fun(0), the call has finished, so the stack allocated to fun(0) is removed. But because there's another call fun(n - 1), another activation record fun(0) is created. This is why see the output pattern above. Counting the number of calls in the diagram, we get 15. Thus, activation records are created and destroyed 15 times.

Thus, where ${n = 3,}$ ${fun(n)}$ is called 15 times. Examining the tree above, there are 4 levels. On the first level, there is only one call — fun(3). On the second level, there are 2 calls — fun(2) and fun(2). On the third level, there are 4 calls, and on the fourth level, there are 8 calls. This corresponds to a geometric sequence:

\lang 1, 2, 4, 8, 16, 32, 64, 128, 256, \ldots \rang

Accordingly, the sum of this sequence is the geometric series ${\sum_{i = 0}^{n} 2^n = 2^{n + 1} - 1.}$ It follows then that the tree recursive function ${f(n)}$ will result in ${2^{n + 1} - 1}$ total calls. Applying complexity analysis, this means the ${f(n)}$ has a time complexity of ${O(2^n).}$

Now, what is the space complexity? To determine space complexity, we ask ourselves, "What is the maximum height of the stack?" Well, we can just look at the tree above. With tree recursive functions, each stack generated is destroyed because once a call has finished it is destroyed. This in turn means that number of levels in the recursive tree corresponds to the height of the stack. For fun(0) the number of levels is 1. For fun(1), the number of levels is 2. For fun(2), the number of levels is 3, and so on. As such, the height of the tree is given by ${n + 1.}$ Applying complexity analysis, we have a space complexity of ${O(n).}$

From this discussion, we can see that tree recursion doesn't perform very well in terms of time — it runs on exponential time. Tree recursion, however, has its place. Some problems are just too difficult to solve with loops. Other problems are so difficult that exponential time is the best we can do. We will see some of these problems in later sections.

Mutual Recursion

In mutual recursion, the recursive function ${f}$ calls a recursive function ${g,}$ and the recursive function ${g}$ calls the recursive function ${f.}$ Generally:

f(n) {
	g(Δn)
}
g(n) {
	f(Δn)
}

For example:

#include <iostream>

void g(int n);

void f(int n) {
if (n > 0) {
	std::cout << "f(" << n << ")" << std::endl;
	g(n - 1);
}
}

void g(int n) {
if (n > 1) {
	std::cout << "g(" << n << ")" << std::endl;
	f(n - 1);
}
}

int main() {
int x = 5;
f(x);
return 0;
}

f(5)
g(4)
f(3)
g(2)
f(1)

Observe the output. When we call f(), we call g(), and when we cal g(), we call f(). Under normal circumstances, such a circular control flow immediately alerts us to an infinite process. But, as with all recursive functions, the approach works because each call is given a smaller and smaller input, and each call has a base case. Visualizing the call as a tree:

Nested Recursion

Because functions are expressions, they can be passed as arguments to functions. Accordingly, given a recursive function ${f,}$ we can pass a call to ${f}$ as an argument for ${f.}$ This is an example of nested recursion.

f(f(Δn)) {...};