Week 1. Recursion

Programming with Recursion

Recursion

Recursion is when a method calls itself. For example, the factorial function.

Link to original

Factorial Function

Factorial Function

The factorial function of $n$ is the product of integers greater than or equal to $n$.

It can be recursively defined as $f(n)=\{\begin{array}{ll}1,& \text{if }n=0\\ n\cdot f(n-1),& \text{if }n\ge 1\end{array}$.

As a Java method:

public static int factorial(int n) {
	if (n <= 0) return 1;
	return n * factorial(n - 1);
}

Iterative solution:

public static int factorial(int n) {
	int result = 1;
 
	for (int i=1;i<=n;i++) {
		result *= i;
	}
 
	return result;
}

Link to original

Visualising Recursion

Recursion Trace

We can draw a recursion trace, where we have a box for each recursive call, an arrow from each caller to callee and an arrow from each callee to caller showing return value.

Here’s an example of the Factorial Function:

digraph {
	start [shape=point]
	4 [label="factorial(4)"]
	3 [label="factorial(3)"]
	2 [label="factorial(2)"]
	1 [label="factorial(1)"]
	0 [label="factorial(0)"]
 
	start->4 [label=" call"]
	4->3 [label=" call"]
	3->2 [label=" call"]
	2->1 [label=" call"]
	1->0 [label=" call"]
 
	0->1 [label=" return 1"]
	1->2 [label=" return 1"]
	2->3 [label=" return 2"]
	3->4 [label=" return 6"]
	4->start [label=" return 24"]
}

Link to original

Recursive Method Structure

Base case (Recursion)

Base case: values of the input variables for which we perform no recursive calls are called base cases (there should be at least one base case and every possible chain of recursive calls must eventually reach a base case)

Link to original

Recursive calls

A recursive call calls the current method, each recursive call should be defined in such a way that it makes progress towards a base case.

Link to original

Linear Recursion

Linear Recursion

A linear recursive function calls itself at most once each time it is run.

To implement a linear recursive function:

1. Test for base cases
   • Begin by testing for a set of base cases (should be at least one).
   • Every possible chain of recursive calls must eventually reach a base case, and the handling of each base case should not use recursion.
2. Recur once
   • Perform a single recursive call
   • This step may have a test that decides which of several possible recursive calls to make, but it should ultimately make just one of these calls.
   • Define each possible recursive call so that it makes progress towards a base case.

Link to original

Example of Linear Recursion (Linear Sum)

Algorithm: LinearSum(A, n) Input: An integer array $A$ and an integer $n\ge 1$, such that $A$ has at least $n$ elements. Output: The sum of the first $n$ integers in $A$.

if n = 1 then
	return A[0]
else
	return LinearSum(A, n-1) + A[n-1]

Example recursion trace over $A=\{4,3,6,2,5\}$ and $n=5$:

digraph {
	start [shape=point]
	4 [label="LinearSum(A, 5)"]
	3 [label="LinearSum(A, 4)"]
	2 [label="LinearSum(A, 3)"]
	1 [label="LinearSum(A, 2)"]
	0 [label="LinearSum(A, 1)"]
 
	start->4 [label=" call"]
	4->3 [label=" call"]
	3->2 [label=" call"]
	2->1 [label=" call"]
	1->0 [label=" call"]
 
	0->1 [label=" return A[0] = 4"]
	1->2 [label=" return 4 + A[1] = 7"]
	2->3 [label=" return 7 + A[2] = 13"]
	3->4 [label=" return 13 + A[3] = 15"]
	4->start [label=" return 15 + A[4] = 20"]
}

Example of Linear Recursion (Reversing Array)

Algorithm: ReverseArray(A, i, j) Input: An array $A$ and non-negative integer indices $i$ and $j$. Output: The reversal of the elements in $A$ starting at index $i$ and ending at $j$.

Example: $A=\{7,2,5,8,9,3,6,1,4\}$; ReverseArray(A, 2, 7); $A=\{7,2,1,6,3,9,8,5,4\}$.

if i < j then
	Swap A[i] and A[j]
	ReverseArray(A, i+1, j-1)
return

Defining Arguments for Recursion

In specifying a recursive method, it is important to define the method in a way that facilities recursion. This sometimes requires we define additional parameters that are passed to the method.

For example, even if we only want to reverse whole arrays, we still define the array reversal method as ReverseArray(A, i, j), not ReverseArray(A).

Computing Powers

The power function, $p(x,n)=x^n$ can be defined recursively as:

$$p(x,n)=\{\begin{array}{ll}1& \text{if }n=0\\ x\cdot p(x,n-1)& \text{else}\end{array}$$

This leads to a power function that runs in time linear in $n$ since we make $n$ recursive calls and $n$ multiplications. But we can go faster than this by using recursive squaring:

$$p(x,n)=\{\begin{array}{ll}1,& \text{if }n=0\\ (p(x,\frac{n}{2}){)}^2,& \text{if }n>0\text{ is even}\\ x\cdot (p(x,\frac{n-1}{2}{)}^2,& \text{if }n>0\text{ is odd}\end{array}$$

if n == 0 then
	return 1
if n is even then
	y = Power(x, x / n)
	return y * y
else
	y = Power(x, (n - 1) / 2)
	return x * y * y

Tail Recursion

Tail Recursion

Tail recursion occurs when a linearly recursive method makes its recursive call as its last step. The array-reversal method is an example. Such methods can easily be converted to non-recursive methods, to save on resources.

Link to original

Binary Recursion

Binary Recursion

Binary recursion occurs whenever there are two recursive calls for each non-base case.

Link to original

Example: Binary Sum

For example, add all numbers in an integer array $A$: Algorithm: BinarySum(A, i, n) Input: An array $A$ and integers $i\ge 0$ and $n\ge 1$ Output: The sum of the $n$ integers in $A$ starting a index $i$

if n = 1 then
	return A[i]
 
return BinarySum(A, i, ceil(n / 2))
	 + BinarySum(A, i + ceil(n / 2), floor(n / 2))

digraph {
	start [shape=point]
	root [label="0,8"]
	left [label="0,4"]
	right [label="4,4"]
	left1 [label="0,2"]
	right1 [label="2,2"]
	left2 [label="4,2"]
	right2 [label="6,2"]
	left3 [label="0,1"]
	right3 [label="1,1"]
	left4 [label="2,1"]
	right4 [label="3,1"]
	left5 [label="4,1"]
	right5 [label="5,1"]
	left6 [label="6,1"]
	right6 [label="7,1"]
 
	root->start
	start->root [label=" 29"]
	
	root->left
	left->root [label=" 13"]
	root->right
	right->root [label=" 16"]
	
	left->left1
	left1->left [label=" 8"]
	left->right1 
	right1->left [label=" 5"]
	right->left2 
	left2->right [label=" 8"]
	right->right2
	right2->right[label=" 8"]
 
	left1->left3
	left3->left1 [label=" 3"]
	left1->right3
	right3->left1 [label=" 5"]
	right1->left4
	left4->right1 [label=" 2"]
	right1->right4
	right4->right1 [label=" 3"]
 
	left2->left5
	left5->left2 [label=" 1"]
	left2->right5
	right5->left2 [label=" 7"]
	right2->left6
	left6->right2 [label=" 4"]
	right2->right6
	right6->right2 [label=" 4"]
}

Example: Computing Fibonacci Numbers

Fibonacci numbers are defined recursively:

$$\begin{array}{rlrl}{F}_0& =0& & \\ F_1& =1& & \\ F_i& =F_{i-1}+F_{i-2}& & \text{for }i>1\end{array}$$

Recursive algorithm (basic) Input: Non-negative integer $k$ Output: $k$-th Fibonacci number $F_k$

if k <= 1 then
	return k
else
	return BinaryFib(k - 1)
		 + BinaryFib(k - 2)

This recursion is inefficient, there are many repetitions of the same computation, such as $\text{fib}(k-2)$ from $\text{fib}(k)$.

Recursive algorithm (efficient) Input: An integer $k\ge 1$ Output: Pair of Fibonacci numbers $(F_k,F_{k-1})$

if k <= 1 then
	return (k, 0)
else
	(i, j) = LinearFib(k - 1)
	return (i + j, i)

public static int[] linearFib(int n) {
	if (n <= 1) return new int[] { n, 0 };
 
	int [] F = linearFib(n - 1);
	return new int[] { F[0] + F[1], F[0] };
}

Multiple Recursion

Multiple Recursion

Multiple recursion occurs whenever there are more than one recursive calls for each non-base case.

Link to original

{
	"url":"[Lecture01 - Introduction, Recursion.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%201/Semester%202/4CCS1DST%20Data%20Structures/Resources/Lecture01%20-%20Introduction%2C%20Recursion.pdf)",
	"page":[47,48,49,50,51],
	"scale": 0.8
}