Recursion: Fibonacci Numbers - Hacker Rank Solution

The Fibonacci Sequence

The Fibonacci sequence appears in nature all around us, in the arrangement of seeds in a sunflower and the spiral of a nautilus for example.

The Fibonacci sequence begins with  and  as its first and second terms. After these first two elements, each subsequent element is equal to the sum of the previous two elements. 

Recursion: Fibonacci Numbers - Hacker Rank Solution 

To solve this challenge, we need to split the challenge into a base case (the point at which we stop performing operations) and a recursive case (the base case is not yet reached, so the function calls itself in such a way that we approach — and eventually reach — the base case).

Base Case

We already know that:

1. We must know the value of two consecutive elements to calculate the value of the next element in the sequence (i.e., ).
3. .

Thus, we consider the base case to be when we reach the first two elements of the series.

Recursive Case

We've already defined our base case, so we define our recursive case to be everything else not satisfying the base case. This means that any other valid value of  (i.e., whenever ) should be handled recursively. So how do we call the function in a way that guarantees we'll eventually reach the base case?

Implementation

Depending on your submission language, the body of your function should look something like this:

Basic Syntax

if(n <= 0) {
    return 0;
}
else if (n == 1) {
    return 1;
}
else {
    return fibonacci(n - 1) + fibonacci(n - 2);
}

This can be reduced to:

if(n > 2) {
    return fibonacci(n - 1) + fibonacci(n - 2);
}
else {
    // This is the equivalent of fibonacci(0) + fibonacci(1) = 0 + 1 = 1
    return 1;
}

Ternary Operators

// ? : Ternary Operator
return (n > 2) ? fibonacci(n - 1) + fibonacci(n - 2) : 1;

# Python/PyPy
return fibonacci(n - 1) + fibonacci(n - 2) if (n > 2) else 1

Java
import java.util.*;

public class Solution {

    public static int fibonacci(int n) {
        return (n > 2) ? fibonacci(n - 1) + fibonacci(n - 2) : 1;
    }
    
    public static void main(String[] args) {
        
        Scanner scanner  = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.close();
        
        System.out.println(fibonacci(n));
        
    }
}