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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Recursion”

  1. Paul said
    March 12, 2019 at 10:55 AM

    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
    March 13, 2019 at 3:36 AM

    A 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' 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
    March 21, 2019 at 6:54 PM

    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

Leave a comment