# fibonacci function python

```# Implement the fibonacci sequence
# (0, 1, 1, 2, 3, 5, 8, 13, etc...)
def fib(n):
if n== 0 or n== 1:
return n
return fib (n- 1) + fib (n- 2) ```

Here is what the above code is Doing:
1. Defining a function called fib that takes in a parameter n.
2. If n is equal to 0 or 1, return n.
3. Otherwise, return the result of fib(n-1) + fib(n-2).

This is a recursive function, meaning that it calls itself.

Recursive functions are useful for solving problems that can be broken down into smaller subproblems.

For example, the fibonacci sequence can be defined as:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2)

The first two cases are easy to solve, but the third case is where things get interesting.

In order to solve fib(n), we need to solve fib(n-1) and fib(n-2).

But in order to solve fib(n-1), we need to solve fib(n-2) and fib(n-3).

And in order to solve fib(n-2), we need to solve fib(n-3) and fib(n-4).

This pattern continues until we reach fib(0) and fib(1), which are easy to solve.

This is an example of a divide and conquer algorithm.

The time complexity of this algorithm is O(2^n), which is not very efficient.

There is a more efficient way to solve this problem using memoization, which we will learn about in the next section.