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.

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