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.

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: