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

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
    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

    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
    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)
                     (rec (1- x) (* acc x)))))
        (rec x 1)))
    (defun fibonacci (x)
      (labels ((rec (a b i)
                 (if (zerop i)
                     (rec b (+ a b) (1- i)))))
        (rec 0 1 (1+ x))))

    Example Usage:

    CL-USER> (factorial 20)
    CL-USER> (fibonacci 100)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: