Naive vs memoised Fibonacci: count the calls
Recursion is when a method solves a problem by calling itself on a smaller version of the same problem, until it reaches a case small enough to answer directly. Every recursive method needs a base case that stops it and a recursive case that moves toward it.
Change the code and press Run (Ctrl+Enter). Try to predict the output first, then break it on purpose and read the error. Your edits are saved and match the lesson page.
Practice questions
Write the code in the editor, run it, then open the model answer to compare.
Write a recursive static int sumTo(int n) that returns 1 + 2 + ... + n. Print sumTo(10) and sumTo(100).
Write a recursive static boolean isPalindrome(String s) that compares the first and last characters and recurses on the middle. Test "level", "racecar" and "java".
Write a recursive static int countOccurrences(int[] arr, int index, int target) that counts how many times target appears from index to the end. Test with {1, 3, 1, 1, 5} and target 1.
Write a recursive static int gcd(int a, int b) using Euclid's rule: gcd(a, 0) = a, otherwise gcd(b, a % b). Print gcd(48, 18) and gcd(17, 5).
Explain it without notes
What are the two parts every recursive method needs, and what goes wrong without each?
Walk through what happens on the call stack when factorial(3) runs.
Why is naive recursive Fibonacci so slow, and how does memoisation fix it?
When would you choose recursion over a loop in Java, and when not?
Does Java optimise tail recursion? What does that mean for your code?
Expected output
fib(25) = 75025 using 242785 calls
fibMemo(25) = 75025 using 49 calls
fibMemo(90) = 2880067194370816120