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)