We write a Recursive method to solve the fibonacci series.

Given a particular value n, we calculate the value of Fibonacci(n) by adding together Fibonacci(n-1) + Fibonacci(n-2).

When do we stop? we need a base case, or stopping condition, and that is when n is <= 1. Then we simply return the value of n and stop recursing.

This allows us to write a simple solution: If n <= 1 return n, otherwise return the value of fibonacci(n-1) + fibonacci(n-2).

In this challenge, however we do not display the calculated value of Fibonacci(n), instead we are going to display the values of n at each recursive call to our method.

So at the very start of our recursive method, we will write fibonacci(n) where n is replaced with the current value of the input to our method. In addition, to illustrate the recursion more clearly, we will indent our output 2 spaces for every level of our recursion.

The example should show what is needed a little more clearly.

Input Format

one single valid java integer

Constraints

0 <= n <= 8

Output Format

output a separate line for each recursion call with the method name fibonacci and the value of n inside the parenthesis: fibonacci(5)

Sample Input 0

4 

Sample Output 0

fibonacci(4) fibonacci(3) fibonacci(2) fibonacci(1) fibonacci(0) fibonacci(1) fibonacci(2) fibonacci(1) fibonacci(0) 

Explanation 0

our input value is 4. For the first call to our method we do not indent. We are at level 0 of our binary tree.

We recurse in the order of fibonacci(n-1) + fibonacci(n-2), so you see that the next output is when we call fibonacci(4-1)

fibonacci(3) does not hit a stopping condition, so it recurses with fibonacci(3-1).

Likewise for fibonacci(2):

It first recurses with fibonacci(2-1) --> 1 is a stopping condition, so there is no more recursion at this point, we return to our method where n was 2.

fibonacci(2) now recurses with fibonacci(2-2) --> 0 is also a stopping condition, so we don't recurse any more. Note that the calls to fibonacci(1) and fibonacci(0) are at the same level of indentation.