Recursion
March 12, 2019
Although we sometimes discuss rather more advanced topics, one focus of this blog will always be on student programmers, so I monitor several internet sites that cater to questions from learners. I have seen several posts in the last week or so about recursion, so I assume that we have reached the point in the semester where programming students are learning about recursion. Most programming professors seem to think that the factorial function (what is the value of n factorial) and the fibonacci function (what is the nth fibonacci number) are good demonstrations of recursion; personnally, I think it is better to discuss recursion in terms of binary trees.
Your task is to write versions of the factorial and fibonacci functions that use recursion to calculate their result. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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: