Recursion in a nutshell
A method that calls itself directly/indirectly is called recursion. This method is known as a recursive method. The famous Fibonacci numbers problem can be implemented recursively, as follows:
int fibonacci(int k) {
// base case
if (k <= 1) {
return k;
}
// recursive call
return fibonacci(k - 2) + fibonacci(k - 1);
}
There are two important parts in this code:
- Base case: Returns a value without subsequent recursive calls. For special input(s), the function can be evaluated without recursion.
- Recursive call: Since the
fibonacci()method calls itself, we have a recursive method.
Recognizing a recursive problem
Before we try to solve a problem via a recursive algorithm, we must recognize it as a good candidate for such an algorithm. Most of the recursive problems used...
