Problem: given an array A[0..n-1] of size n of numbers, compute the sum of the numbers in A ---------------------------------------- Recursive (non tail recursive!) solution: ---------------------------------------- sum(A,i,n) // i = where it is, n = length of A if i = n then 0 else A[i] + sum(A,i+1,n) Space analysis: it uses O(n) cells of memory for the call stack In detail: every call allocates cells for A,i,n and the return address ------------------------ Tail recursive solution: ------------------------ Idea: because I want to do tail recursion, I should pass to the recursive call knowledge about all the part of the structure I have already visited. In this case, this knowledge is the sum of the elements I have already visited. Let's call it acc for accumulator. sum(A,i,n,acc) if i = n then acc else sum(A,i+1,n,acc+A[i]) Example: A = [2,2,3,4,5] sum(A,0,.,0) = sum(A,1,.,0+A[0] = 2) = sum(A,2,.,2+A[1] = 4) = sum(A,3,.,7) = sum(A,4,.,11) = sum(A,5,.,16) = Space analysis: it uses O(1) memory cells (the stack does not grow) 16 ------------------------ Non recursive solution: ------------------------ sum(A,n) acc = 0 for i = 0 to n - 1 acc := acc + A[i] acc