Recursion, Nested Subprograms & Expression Functions

Write recursive subprograms (factorial, Fibonacci, mutual recursion with forward declarations), use nested subprograms that access enclosing variables, write expression functions with conditional expressions, and understand stack usage and Storage_Error.

Ada fully supports recursion and nested subprograms. Nested (local) subprograms can see the variables of the subprograms that contain them, which gives you a structured alternative to global variables. Recursion is natural for tree structures and divide-and-conquer algorithms, and Ada's range checks catch overflow in recursive arithmetic instead of letting it wrap.

Recursion

A subprogram may call itself. Each call gets its own copy of parameters and local variables on the stack. Always make progress toward a base case. Mutually recursive subprograms (A calls B, B calls A) need a forward declaration of the second one before the first body. Deep recursion can exhaust the stack, raising Storage_Error; for tasks, the stack size is configurable. Typed parameters such as N : Natural document and enforce that negative input is invalid.

• Recursion is fully supported; each call has its own frame. • Mutual recursion: forward-declare the second subprogram. • Stack exhaustion → Storage_Error. • Use Natural/Positive parameters to rule out invalid inputs.

Nested Subprograms and Expression Functions

A subprogram declared inside another can read and update the enclosing subprogram's local variables (up-level references). This keeps helpers private to the only place that uses them and avoids passing long parameter lists. Expression functions combined with conditional expressions give compact recursive definitions such as Factorial (N) is (if N = 0 then 1 else N * Factorial (N - 1)).

• Nested subprograms see enclosing locals. • Keep helpers local to their only user. • Expression functions + if-expressions → concise recursive definitions.

Code Examples

Factorial and the mutually recursive Is_Even/Is_Odd are expression functions; Fibonacci is a classic recursive function; Show is nested inside Print_Powers and reads its Value variable. 13! = 6,227,020,800 exceeds Integer'Last, so Constraint_Error is raised instead of a wrong result. Output: 10! = 3628800 Fibonacci 0..10: 0 1 1 2 3 5 8 13 21 34 55 Is_Even (7) = FALSE Powers of 3: 3 9 27 81 243 13! overflows Integer: Constraint_Error function F (N: Integer) return Integer is (N * F (N - 1)); -- no base case function F (N: Natural) return Positive is (if N = 0 then 1 else N * F (N - 1));

Without a base case recursion never stops and ends in Storage_Error.

function Is_Even (N: Natural) return Boolean is (if N = 0 then True else Is_Odd (N - 1)); function Is_Odd... -- used before declared function Is_Odd (N: Natural) return Boolean; -- forward declaration first

Everything must be declared before use; forward-declare for mutual recursion.

-- naive Fibonacci (40) inside a tight loop -- iterate or memoize for large N

Naive double recursion is exponential; iterate for performance.

Which exception signals stack exhaustion from deep recursion? A. Constraint_Error B. Storage_Error C. Program_Error D. Tasking_Error

Why does mutual recursion need a forward declaration? A. Performance B. Ada requires declaration before use C. To enable inlining D. It doesn't B. Ada requires declaration before use.

Can a nested procedure modify its enclosing procedure's local variable? A. Yes B. No C. Only constants D. Only through pointers

A. Yes — up-level references are allowed.

What happens when Factorial (13) is computed with Integer? A. Wrong value B. Constraint_Error C. 0 D. Storage_Error

B. Constraint_Error — overflow is detected (verified in the example).

Trace the recursion example.

Real output: 10! = 3628800 Fibonacci 0..10: 0 1 1 2 3 5 8 13 21 34 55 Is_Even (7) = FALSE Powers of 3: 3 9 27 81 243 13! overflows Integer: Constraint_Error

Write a recursive function Power (Base : Integer; Exp : Natural) return Integer using fast exponentiation.

function Power (Base : Integer; Exp : Natural) return Integer is begin if Exp = 0 then return 1; elsif Exp mod 2 = 0 then declare Half : constant Integer := Power (Base, Exp / 2); begin return Half * Half; end; else return Base * Power (Base, Exp - 1); end if; end Power;

Squaring the half power gives O(log Exp) recursive calls; overflow is still detected by Ada's checks.

with Ada.Text_IO; use Ada.Text_IO;

procedure L17_Recursion is

   function Factorial (N : Natural) return Positive is
     (if N = 0 then 1 else N * Factorial (N - 1));

   function Fibonacci (N : Natural) return Natural is
   begin
      if N < 2 then
         return N;
      end if;
      return Fibonacci (N - 1) + Fibonacci (N - 2);
   end Fibonacci;

   --  Mutual recursion needs a forward declaration.
   function Is_Odd (N : Natural) return Boolean;
   function Is_Even (N : Natural) return Boolean is
     (if N = 0 then True else Is_Odd (N - 1));
   function Is_Odd (N : Natural) return Boolean is
     (if N = 0 then False else Is_Even (N - 1));

   --  A nested helper that uses the enclosing procedure's local variable.
   procedure Print_Powers (Base : Positive) is
      Value : Positive := 1;
      procedure Show is
      begin
         Put (Integer'Image (Value));
      end Show;
   begin
      for I in 1 .. 5 loop
         Value := Value * Base;
         Show;
      end loop;
      New_Line;
   end Print_Powers;
begin
   Put_Line ("10! =" & Integer'Image (Factorial (10)));
   Put ("Fibonacci 0..10:");
   for I in 0 .. 10 loop
      Put (Integer'Image (Fibonacci (I)));
   e
…