(πΒ 40 mins)
<aside> π recursion: a technique of programming where a function calls itself (directly or indirectly)
</aside>
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:
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);
}
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>