Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation
• 19
BFS

• # Branching factors

When dealing with recursive functions, it sometimes makes sense to call the current function several times with different arguments. For example, if we would calculate the n-th Fibonacci number with a recursive function, that might look something like this:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
Here, for each argument n, we make 2 recursive calls to the function fib with arguments n-1 and n-2.

### Challenge - Recursive Fibonacci

Count the number of times the recursive Fibonacci function is called.

#### Input

The input contains a single integer n (0 ≤ n ≤ 20).

#### Output

The program should print the number of times the fib function was called.

#### Examples

 Input Output 0 1 1 1 2 3 5 15 6 25

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB