Recursion: Fibonacci Numbers Solution (Python Language)

 The Fibonacci Sequence.

The Fibonacci Sequence appears in nature all around us, in the arrangement of seeds in a sunflower and spiral of a nautilus For Example .

The Fibonacci Sequence begins with fibonacci(0) = 0 and fibonacci(1) = 1 as its first and second terms. After these first 2 elements, each subsequent element is equal to the previous 2 elements.

Programmatically:

    fibonacci(0) = 0

    fibonacci(1) = 1

    fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

Given n, return the nth number in the sequence.

As an example, n = 5. The Fibonacci sequence to 6 is fs = [0,1,1,2,3,5,8]. With zero-based indexing, fs[5] = 5.

Function Description

Complete the recursive function fibonacci in the editor below. It must return the nth element in the Fibonacci sequence.

fibonacci has the following parameter(s):

    n: the integer index of the sequence ti return

Input Format

The input line contains a single integer,n.

Constraints

    0<n<=30

Output Format

Locked stub code in the editor prints the integer value returned by the fibonacci function.

Sample Input

    3

Sample Output

    2

Explanation

The Fibonacci sequence begins as follows:

    fibonacci(0) = 0

    fibonacci(1) = 1

    fibonacci(2) = 1

    fibonacci(3) = 2

    fibonacci(4) = 3

    fibonacci(5) = 5

    fibonacci(6) = 8

...

We want to know the value of fibonacci(3). In the sequence above, fibonacci(3) evaluates to 2.

Solution Below Here:

def fibonacci(n):

    if n<0: 

        print("Incorrect input") 

    # First Fibonacci number is 0 

    elif n==1: 

        return 0

    # Second Fibonacci number is 1 

    elif n==2: 

        return 1

    else: 

        return fibonacci(n-1)+fibonacci(n-2) 

n = int(input())

print(fibonacci(n+1))