Recursive Fibonacci sequence

Question

I’m studying Java and I need to do a recursive Fibonacci program, but I have no idea how to do that. Please, if you know, help me. Here’s an inductive code:

 public static void main(String[] args) {
    int n = 5, i = 0, a = 0, b = 1;
    System.out.print( a + " " + b + " ");
    while(i<=n){
        int c = a + b;
        System.out.print(c + " ");
        a = b;
        b = c;
        i++;
    }
}

Answer 1

The recursive call to Fibonacci is quite simple:

class Fibonacci {
    public static long fibonacci(int n) {
        return n < 2 ? n : fibonacci(n - 2) + fibonacci(n - 1);
    }

    public static void main(String[] args) {
        for (int i = 0; i <= 10; i++) {
            System.out.println("Fibonacci(" + i + ") = " + fibonacci(i));
        }
    }
}

Here’s the way out:

Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8
Fibonacci(7) = 13
Fibonacci(8) = 21
Fibonacci(9) = 34
Fibonacci(10) = 55

See here working on ideone.

However, Fibonacci is a classic example of a problem where the use of recursion is a very bad strategy and performs poorly. The use by iteration (with while or for) is quite superior. See more details on this in this other answer of mine.