Naive vs Iterative Summing

Naive recursive summing: nsum

let rec nsum n =
  if n = 0 then 0
  else n + nsum (n - 1)
(* val nsum : int -> int = <fun> *)

The function computes $1 + 2 + \dots + n$ by recursion. A trace for nsum 3:

nsum 3 => 3 + (nsum 2)
       => 3 + (2 + (nsum 1))
       => 3 + (2 + (1 + (nsum 0)))
       => 3 + (2 + (1 + 0))
       => 6

The nesting of parentheses is not just notation — it indicates a real problem. The function gathers up numbers, but none of the additions can be performed until nsum 0 is reached. Meanwhile, the computer must store pending values on the call stack. For large n, say nsum 10000, the computation might fail due to stack overflow.

Iterative summing with accumulator: summing

let rec summing n total =
  if n = 0 then total
  else summing (n - 1) (n + total)
(* val summing : int -> int -> int = <fun> *)

The additional argument total is a running total (called an accumulator). If n is zero, it returns the accumulator; otherwise it adds n and continues. The trace:

summing 3 0 => summing 2 3
            => summing 1 5
            => summing 0 6
            => 6

The recursive calls do not nest — additions are done immediately as we go along. No stack of pending work builds up.

Comparison

Function	Recursion pattern	Stack usage
nsum	Nested: work deferred	Grows with n
summing	Flat: work done immediately	Constant

The arithmetic progression formula

The sum can be computed in O(1) time using:

$1 + 2 + \dots + n = \frac{n(n+1)}{2}$

This is obviously the best approach if only the sum is needed. The recursive versions illustrate general patterns: naive recursion builds up deferred work, while accumulator-based iteration processes elements as it goes.

When nesting matters

The nesting in nsum is a specific instance of a general problem: if each recursive call must wait for the result of the next call, the intermediate values accumulate. Functions that avoid this are called iterative or tail-recursive.