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.

Advertisements

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

    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

    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 Reply

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

WordPress.com Logo

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

Google photo

You are commenting using your Google 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: