Recursion in Ada

Ada supports recursive functions. Here’s a classic example.

with Ada.Text_IO; use Ada.Text_IO;

procedure Recursion is

   -- This Fact function calls itself until it reaches the
   -- base case of Fact(0).
   function Fact (N : Natural) return Natural is
   begin
      if N = 0 then
         return 1;
      else
         return N * Fact (N - 1);
      end if;
   end Fact;

   -- Recursive functions can also be declared locally
   function Fib (N : Natural) return Natural is
   begin
      if N < 2 then
         return N;
      else
         return Fib (N - 1) + Fib (N - 2);
      end if;
   end Fib;

begin
   Put_Line (Natural'Image (Fact (7)));
   Put_Line (Natural'Image (Fib (7)));
end Recursion;

In this Ada example, we define two recursive functions: Fact for calculating factorials and Fib for generating Fibonacci numbers.

The Fact function is defined at the procedure level, while Fib is defined locally within the main procedure body. Both functions demonstrate the use of recursion in Ada.

To run this program, save it as recursion.adb and use the following commands:

$ gnatmake recursion.adb
$ ./recursion
 5040
 13

Ada doesn’t have closures in the same way as some other languages, so we’ve represented the recursive Fibonacci function as a local function instead. This achieves a similar effect of having a locally scoped recursive function.

The output shows the factorial of 7 (5040) and the 7th Fibonacci number (13), demonstrating that both recursive functions are working correctly.