Recursion

Key Concepts

• Non-Linear Recursion (e.g., Fibonacci)
• Linear Recursion
• Tail Recursion

Non-Linear Recursion

A Classic Example: Calculating Fibonacci Numbers

    fib :: Int -> Int
    fib 0 = 0
    fib 1 = 1
    fib n = (fib (n - 1)) + (fib (n - 2))

(We could have a guard to ensure that n > 1, otherwise generate an error.)

See this Fibonacci Animations (PowerPoint) presentation to see the problems that can arise from implementing recursive mathematical definitions directly.

What does this do?

⇓ (see details)

Linear Recursion

A function is linearly recursive if it recursively calls itself only once.

A Classic Example: Calculating N Factorial

    factorial :: Int -> Int
    factorial 0 = 1
    factorial 1 = 1
    factorial n = n * (factorial (n - 1))

(Again, we could have a guard to ensure that n > 1, otherwise generate an error.)

What does this do?

    factorial 5 = 5 * factorial 4
                = 5 *   4 * factorial 3
                = 5 *   4 *   3 * factorial 2
                = 5 *   4 *   3 * 2 * factorial 1
                = 5 *   4 *   3 * 2 * 1         (now we start the calculations)
                = 5 *   4 *   3 * 2
                = 5 *   4 *   6
                = 5 *  24
                = 120

Tail Recursion

A linear recursive function is tail recursive if it does all its work on the way "down" (in determining the parameters to the recursive call), and not on the way back "up". The factorial example above is not tail recursive. To turn a function into one that is tail recursive, we often introduce a helper function, as in the example below.

A Tail Recursive version of the Factorial function

    factorial :: Int -> Int
    factorial 0 = 1
    factorial 1 = 1
    factorial n = factHelper n 1
        where factHelper :: Int -> Int -> Int
              factHelper 1 intermed = intermed
              factHelper n intermed = factHelper (n - 1) (n * intermed)

(Again, we could have a guard to ensure that n > 1, otherwise generate an error.)

What does this do?

    factorial 5 = factHelper 5 1
                = factHelper 4 (5 * (1))
                = factHelper 3 (4 * (5))
                = factHelper 2 (3 * (20))
                = factHelper 1 (2 * (60))
                = 120  (and this result just gets passed up the chain)