A recursive function is a function that calls itself.
Some coders love recursion, they even make jokes about it. The GNU operating system uses a recursive acronym: GNU stands for "GNU's Not Unix!"
These notes have been written using a program called Emacs. There used to be two programs based on Emacs called EINE and ZWEI. As well as being the German words for One and Two, EINE is a recursive acronym for "EINE Is Not Emacs", and ZWEI is a recursive acrynom for "ZWEI Was Eine Initially".
Some coders hate recursion. That might be because they haven't taken the time to practice it, and we fear what we don't understand.
However sometimes they hate recursion because of Bad Recursion.
Here's a recursive function to work out the nth term in the Fibonacci sequence
```python
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n-1) + fib(n-2)
```
There's a lot to like about this function, it's easy to understand, it practically tells you what it does (at least it does if you understand recursion)
The trouble is, it's very slow. If you enter fib(33) there'll be a perceptible lag before the answer appears.
The following iterative function for working out Fibonacci numbers isn't quite so easy to understand, but it produces no such lag
```python
def fibo(n):
x,y = 1,1
for i in range(n-1):
x,y = y,x+y
return x
```
Why does the recursive function take so long?
If you think about it, you can see why. According to the recursive code
```python
fib(33) = fib(32) + fib(31)
= fib(31) + fib(30) + fib(30) + fib(29)
= fib(30) + fib(29) + fib(29) + fib(28) + fib(29) + fib(28) + fib(28) + fib(27)...
```
etc.
You're asking the computer to perform 2^32 or 4294967296 operations.
You can use timeit to compare how long it takes the two functions take to execute. Here's an example:
```python
import timeit
def fib(n):
if n == 1 or n == 2:
return 1
return fib(n-1) + fib(n-2)
def fibo(n):
x,y = 1,1
for i in range(n-1):
x,y = y,x+y
return x
start_time = timeit.default_timer()
print(fib(32))
print("Recursive function time ", timeit.default_timer() - start_time)
start_time = timeit.default_timer()
print(fibo(32))
print("Iterative function time ", timeit.default_timer() - start_time)
```
Look how much faster the iterative function runs: A fraction of a fraction of a second.
```python
>>> 2178309
Recursive function time 0.8230643309998413
2178309
Iterative function time 1.5395999980682973e-05
```
There are ways to speed up recursion, and there are times when recursion is exactly the way to solve the problem, but for the moment remember this rule: iteration is *always* faster than recursion.