0. Table of Contents

1. Compilation 🧩

2. Makefiles ⚒️

3. Recursion 🔁

(🕑 40 mins)

<aside> 📘 recursion: a technique of programming where a function calls itself (directly or indirectly)

</aside>

3.1. recursion: the concept 💭

to understand the concept of recursion, it may be helpful to explore some examples of recursive definitions (where something is defined in terms of itself)

e.g. factorial — $n! = n \times (n - 1)!$, and also $0! =1$

e.g. Fibonacci sequence — the $n$th term of the Fibonacci sequence is given by

$F_n = F_{n-1} + F_{n-2}$, and also $F_1 = 1$ and $F_2 = 1$

e.g. linked lists — a linked list can be defined as either a node that contains a pointer to a linked list, or NULL

notice how all of these recursive definitions have two elements:

1. a definition that is in terms of itself, relating larger cases to smaller cases (the recursive part)
2. a starting point or points (called a base case(s))

3.2. walking through a recursive algorithm: Fibonacci 👣

int fibonnaci(int n) {
	int prevprev = 0;
	int prev = 1;
	int curr = 1;

	for (int i = 2; i < n; i++) {
		prevprev = prev;
		prev = curr;
		curr = prevprev + prev;
	}

	return curr;
}

int fib(int n) {
	// these are the base cases
	// 0th term is zero
	// 1st term is one
	if (n <= 0) return 0;
	if (n == 1) return 1;

	// this is the recursive case
	return fib(n - 1) + fib(n - 2);
}

3.3. writing recursive solutions ✏️

Obviously there is no singular way to solve programming problems, but here is a framework to help you ‘think recursively’.

<aside> ❗ most recursive solutions involve breaking up the problem into subproblems (smaller instances of the same problem)

</aside>

3.3.1. a helpful thinking framework 🏗️

1. identify the simplest case (the base case)