Nth Fibonacci Number Using Recursion

Nth Fibonacci Number Using Recursion

Compute the Nth Fibonacci number recursively and discuss its exponential time complexity.

Input format

A single integer N (1 ≤ N ≤ 28). F(1) = 1, F(2) = 1.

Output format

Print the Nth Fibonacci number.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

1

1

2

1