Fibonacci numbers

Statement

Given a non-negative integer

$n$ , print the

$n$ th Fibonacci number. Do this by writing a function fib(n) which takes the non-negative integer

$n$ and returns the

$n$ th Fibonacci number.

Don't use loops, use the flair of recursion instead. However, you should think about why the recursive method is much slower than using loops.

In all the problems input the data using input() and print the result using print().

1
2
# Read an integer:
# a = int(input())
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Input:

1
6
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Output:

1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX