recursion can make your programs easier to write or understand

❗not quicker and often uses a lot more memory

recursion = a programming pattern where a function calls itself

• typically, we can use recursion as an alternative to ‘looping’

e.g. factorial function can be written using recursion

int factorial(int n) {
	if (n == 0) return 1; // base case

	return n * factorial(n - 1); // recursive step
}

• this factorial function will call a bunch of functions on the stack until it reaches the base case, and then each function will return to the one above it etc. (called unwinding)

base case = a ‘starting point’ that prevents the function from recursing infinitely

recursive case = the step where the function calls itself

• a nice program to visualise how recursion works

<aside> ❗ without the base case, the function will recurse infinitely ⇒ segmentation fault

</aside>

e.g. Fibonacci

iterative solution

int fibonacci(int n) {
	if (n == 1) return 0;
	if (n == 2) return 1;

	int prevprev = 0;
	int prev = 1;
	int current = -1;

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

	return current;
}

recursive solution

int fibonacci(int n) {
	if (n == 1) return 0;
	if (n == 2) return 1;

	return 
		fibonacci(n - 1) + 
		fibonacci(n - 2);
}

observations:

• recursive solution is much easier to write
• but each Fibonacci function will call two additional Fibonacci functions