Normal view

Before yesterdayNews from the Ada programming language world

Recursion โ implementing sum

23 May 2023 at 03:06

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;
```
• 23 May 2023 at 03:06