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.
Programming Praxis 
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 1A Haskell version.
-- 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' 345Here’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: