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;

Advertisement