Recursion is when you write a function that calls itself.
To make a recursive algorithm: Start big, with your complete problem, and trim the problem down step-by-step until you reach the most basic building block of it.
Format
myRecursiveFunction(inputValue)
begin
if evaluateBaseCaseCondition(inputValue)=true then
return baseCaseValue;
else
/*
Recursive processing
*/
recursiveResult = myRecursiveFunction(nextRecursiveValue); //nextRecursiveValue could be as simple as inputValue-1
return recursiveResult;
end if
end
int subtractOneUntilZero(int number) { // Problem: you have a number. You want to count down each number until you reach 0.
if (number == 0) { // Base case: 0. After number goes down to 0, it will stop.
return number;
}
else {
return subtractOneUntilZero(number - 1); // Recursive step. If number hasn't reached 0 yet, how do you get it one step closer to 0? Subtract 1 and repeat.
}
}
```java
// Example: Find the i'th number of the Fibonacci sequence.
int Fibonacci(int i) {
if (i == 0) return 0; // 0, 1, ...
if (i == 1) return 1;
// Re-call the function on the two previous numbers of the sequence, until you reach fib(0) or fib(1).
return Fibonacci(i - 1) + Fibonacci(i - 2);
}
```
- Red boxes = active function calls. These calls are currently executing and occupying space on the call stack.
- When a Fibonacci number is computed, its box turns white.
- Order: Bottom right f(1) => f(0) => f(2) => f(1) => f(3) => …
You can optimize a recursive algorithm by adding caching:
- When a new Fibonacci number is computed, it’s saved to a cache [far right path].
- The next time that Fibonacci number is called, it’s fetched from the catch [blue box]. This saves you from doing a bunch of recursive calls [red crosses].
- For very large numbers, e.g. f(50), this saves you from repeating a bunch of recursive function calls.
- Each node crossed out is some storage space and execution time you saved.
Every problem that’s solved recursively can also be solved iteratively.
Choosing between an iterative and recursive solution to a problem is a tradeoff between efficiency and complexity.
fib(5)). Then go down, splitting up the problem into smaller parts, until you reach your base cases (fib(0,1)). Then build back up.
fib(0, 1). Then go up, solving incrementally larger problems (fib(2) = fib(0) + fib(1), fib(3) = fib(2) + fib(1), …) until you reach your complete problem fib(5).Memoization. This is implemented recursively.
Create a class that holds a HashMap.
i and stores fib(i), the corresponding term in the Fibonacci sequence. (i starts at 0)Whenever you perform Fib(i), check if the key i is in the HashMap.
If it isn’t, compute it normally, using recursion.
class FibbonaciCalculator {
// Key = location in Fibonacci sequence, Value = term value
private HashMap<Integer, Integer> map = new HashMap<>();
public int fib(int i) {
// Base cases
if (i == 0 || i == 1) {
return i; // fib(0) = 0, fib(1) = 1
}
// Check if HashMap contains fib(i).
if (map.containsKey(i)) {
return map.get(i); // Get fib(i) and exit recursive call.
}
// If fib(i) is new:
int result = fib(n - 1) + fib(n - 2); // Recursively compute it.
map.put(n, result); // Store in HashMap
return result; // Get fib(i) and exit recursive call.
}
}
Tabulation. This is implemented iteratively.
Start with the base cases. Store them to some variables.
Loop through all non-base cases, up to the complete problem (fib(n)).
After completing the loop, return the final solution you computed.
int Fibonacci(int i) {
if (i == 0) return 0;
int previousBy2 = 0; // Base cases: 0, 1, ...
int previous = 1;
for (int i = 2; i < n; i++) {
int next = previous + previousBy2; // Compute next Fibonacci number.
// Move previous numbers up 1 spot in the sequence.
previousBy2 = previous;
previous = next;
}
// Return the computed Fibonacci number
return previous + previousBy2;
}