Non-TCO recursive example

First, we'll look at the imperative example:

rSum :: [Integer] -> Integer
rSum (x:xs) = x + (rSum xs)
rSum [] = 0

Note that x:xs means we store the head of the list in x and the rest of the list is in xs.

Our goal: To recursively sum the numbers in the list [1, 2, 3].

Each call to rSum needs to get the return value of the recursive call and add it to its x parameter before it can return. This means that each function must stay on the stack longer than the frame of any function that it calls. We had to create four stack frames to sum three numbers. Imagine the amount of RAM storage that this implementation will require when we process lists with a lot of values. Without TCO the our implementation will require O(n) of RAM storage space, based on the number of items in the list. (See Big-Oh notation in Chapter 10, Monads, Type Classes, and Generics)