# Recursion – implementing sum

There are lots of easy to understand recursive algorithms. One of the easiest is is a function `sum(x)`

which sums up all the integers from 1 to `x`

. Here is the function implemented in Ada.

function sum(n: integer) return integer is begin if n = 1 then return 1; else return (n + sum(n-1)); end if; end sum;

Here the function `sum(x)`

recurses until the value of `x`

becomes 0. At this point the recursion is essentially done, and the calls to `sum()`

backtrack. This is shown in the summary below for `sum(5)`

.

sum(5) = (5 + sum(4)) recursive call sum(4) = (5 + (4 + sum(3))) recursive call sum(3) = (5 + (4 + (3 + sum(2)))) recursive call sum(2) = (5 + (4 + (3 + (2 + sum(1))))) recursive call sum(1), return 1 = (5 + (4 + (3 + (2 + 1)))) return (2 + 1) = (5 + (4 + (3 + 3))) return (3 + 3) = (5 + (4 + 6)) return (4 + 6) = (5 + 10) return (5 + 10) = 15

There are *four* recursive calls to `sum()`

in addition to the original call, which is not considered recursive, because the function may actually terminate, e.g. if `sum(1)`

is invoked. So if the function were to call `sum(10000)`

, there would be 9,999 recursive calls. The problem with recursion of course is that many of these simplistic algorithms are just as easy to implement as iterative algorithms.

Here is the same algorithm represented iteratively:

function sumi(n: integer) return integer is s : integer; begin s := 0; for i in 1..n loop s := s + i; end loop; return s; end sumi;