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

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
}

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

recursive case = the step where the function calls itself

<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: