# 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

# Recursion โ Compound Interest (in Ada)

6 March 2023 at 15:28

It might seem odd to think of a compound interest as a problem which could be solved by recursion, but it does make sense. The algorithm for calculating compound interest is of course very simple:

```interest = current_balance ร interest_rate
new_balance = current_balance + interest
current_balance = new_balance```

Of course this calculation is done numerous times depending on how many times the interest is to be compounded. If we were to write a simple function in Ada it would look like this:

```with text_io; use text_io;

procedure compound is
newBal, currBal, intRate, monRate : float;
numMon : natural;

function compound_interest(bal: float; intr: float; n: natural) return float is
interest: float;
newbal: float := bal;
begin
for i in 1..n loop
interest := newbal * intr;
newbal := newbal + interest;
end loop;
return newbal;
end compound_interest;

begin
put("Balance (\$)? "); new_line;
get(currBal); skip_line;
put("Interest rate (e.g. 5.3)? "); new_line;
get(intRate); skip_line;
put("Number of months (1-12)? "); new_line;
get(numMon); skip_line;

monRate := intRate / 100.0 / 12.0;
newBal := compound_interest(currBal,monrate,numMon);
put("The new balance is \$");
put(newBal, 1, 2, 0);
end compound;
```

Here is the program running:

```Balance (\$)?
1000
Interest rate (e.g. 5.3)?
5
Number of months (1-12)?
12
The new balance is \$1051.16```

This nonrecursive procedure is fine, but we can also solve it recursively. If we say that the balance, `b`, after 0 months is the amount of the original deposit, `d`, and the interest rate is `r`, then we can write:

```At month 0: b(0) = d
At month 1 : b(1) = b(0) + b(0) * r
At month 2 : b(2) = b(1) + b(1) * r
...```

Then we can form a recursive definition of the form:

`b(m) = b(m-1) + b(m-1) * r`

Therefore we can use this to create a recursive function:

```b(0) = d
b(m) = b(m-1) + b(m-1) * r```

Here is a recursive version of the function `compound_interest()`.

```function compound_interestR(bal: float; intr: float; n: natural) return float is
newbal: float;
begin
if n = 0 then
return bal;
elsif n = 1 then
return bal + bal * intr;
else
newbal := compound_interestR(bal,intr,n-1);
return newbal + newbal * intr;
end if;
end compound_interestR;
```
• 6 March 2023 at 15:28