Why are parameter based definitions more efficient than recursion?

Question

I have a recursive function sumdown :: Int -> Int that returns the sum of all natural numbers from its argument down to zero e.g. sumdown 3 should return the sum 3+2+1+0 = 6.

sumdown :: Int -> Int
sumdown 0 = 0
sumdown x = x + sumdown(x-1)

I also have this definition which I dont fully understand, could someone please evaluate this for me and tell me why its potentially more efficient than the definition above?

sumdown n = sumd n 0
sumd 0 a = a
sumd n a = sumd (n-1) (n+a)

Thanks.

Answer 1

The first recursion sums values [0..n] starting from its end (n), like this:

1+(2+(3+(... + ((n-1) + n)) ...)))

With this approach, the program first has to enumerate all the numbers, generating the full sequence, and only after that additions can actually be performed.

This requires O(n) memory and O(n) time.

In the second recursion, we count from 0 to n as we did earlier, but now we sum numbers as we go, like in

(((1+2)+3)+4)+ ...

We can sum 1+2 before we count up to 3. After that, we can keep only the result of the previous sum 1+2, and discard the numbers 1 and 2 from memory. Hence, in the whole process we only keep in memory 1) the result of the sum of the numbers met so far, and 2) the next number in the sequence.

Hence, we now require only O(1) memory and O(n) time.

Note: since Haskell is lazy, the above argument holds only if the partial sum is actually forced at every recursion. This forcing might be silently added by the compiler optimizer, but it's a good idea to be explicit about it, e.g. in

sumdown n = sumd n 0
sumd 0 !a = a
sumd n !a = sumd (n-1) (n+a)
-- here I am using the BangPatterns extension,
-- otherwise, seq can be used instead

The second recursion is usually called "accumulator-style", which is a specific case of "tail recursion".

(Note 2: tail recursion is not always a good idea in a lazy language like Haskell, but if the data passed around is simple, e.g. like numbers and not like lists, tail recursion is usually beneficial.)