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