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;

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;
with ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with ada.Float_Text_IO; use Ada.Float_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;