## Recursion

### March 12, 2019

The factorial function is easily written in recursive form:

```(define (factorial n)
(if (zero? n) 1
(* n (factorial (- n 1)))))```

That’s not tail recursive, because the result of the recursive call to `fact` is then multiplied by n. So this is a better version of the function, where the inner `fact` function is tail recursive:

```(define (factorial n)
(let fact ((n n) (result 1))
(if (zero? n) result
(fact (- n 1) (* n result)))))```

The result is the same in either case:

```> (factorial 7)
5040```

The recursive version of the fibonacci function is based on the mathematical definition of the function:

```(define (fibonacci n)
(if (< n 2) 1
(+ (fibonacci (- n 1))
(fibonacci (- n 2)))))```

That function has an O(2n) time complexity; even a calculation as small as `(fibonacci 50)` is extremely slow:

```> (time (fibonacci 50))
(time (fibonacci 50))
no collections
360.035843217s elapsed cpu time
361.197806893s elapsed real time
0 bytes allocated
20365011074```

That took six minutes! We can make it faster by building up the entire fibonacci sequence to n in time proportional to O(n):

```(define (fibonacci n)
(let fib ((k 1) (fk 1) (fk-1 1))
(if (= k n) fk
(fib (+ k 1) (+ fk fk-1) fk))))```
```> (time (fibonacci 50))
(time (fibonacci 50))
no collections
0.000000567s elapsed cpu time
0.000000000s elapsed real time
0 bytes allocated
20365011074```

Wow! It’s possible to do even better, computing the nth fibonacci number in time O(log n), but that’s more to do with mathematicians than with student programmers; you can see how we did it in a previous exercise.

You can run the program at https://ideone.com/W3ba7C.

Pages: 1 2

### 3 Responses to “Recursion”

1. Paul said

In Python. I add a lru_cache for fibonacci, as otherwise it may never finish. I try to avoid recursion in Python, as there is also a recursion limit in Python.

```from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
return fibonacci(n-1) + fibonacci(n-2) if n >= 2 else n

def factorial(n):
return n * factorial(n-1) if n != 0 else 1
```
2. Globules said

```-- Factorial.  Undefined for negative numbers.
fact :: Integral a => a -> a
fact 0 = 1
fact n = n * fact (n-1)

-- Fibonacci.  Undefined for negative numbers.
fib :: Integral a => a -> a
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

-- A faster, yet still recursive, Fibonacci function.  Undefined for negative
-- numbers.
fib' :: Integral a => a -> a
fib' n = go n 0 1
where go i x y | i < 2     = i
| otherwise = x + go (i-1) y (x+y)

main :: IO ()
main = do
print \$ map fact [0..11]

print \$ map fib  [0..11]
print \$ map fib' [0..11]

print \$ fib' 345
```
```\$ time ./recursion
[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800]
[0,1,1,2,3,5,8,13,21,34,55,89]
[0,1,1,2,3,5,8,13,21,34,55,89]
563963353180680437428706474693749258212475354428320807161115873039415970

real    0m0.022s
user    0m0.002s
sys     0m0.006s
```
3. Daniel said

Here’s a solution in Common Lisp.

```(defun factorial (x)
(labels ((rec (x acc)
(if (= 0 x)
acc
(rec (1- x) (* acc x)))))
(rec x 1)))

(defun fibonacci (x)
(labels ((rec (a b i)
(if (zerop i)
a
(rec b (+ a b) (1- i)))))
(rec 0 1 (1+ x))))
```

Example Usage:

```CL-USER> (factorial 20)
2432902008176640000
CL-USER> (fibonacci 100)
573147844013817084101
```