Recursion, Nested Routines & Forward Declarations

A routine that calls itself must have a base case:

13.1 Recursion

A routine that calls itself must have a base case:

function Factorial(N: Integer): Int64;
begin
  if N <= 1 then
    Result := 1
  else
    Result := N * Factorial(N - 1);
end;

function Fib(N: Integer): Int64;      // exponential time — fine for teaching only
begin
  if N < 2 then Result := N
  else Result := Fib(N - 1) + Fib(N - 2);
end;

function GCD(A, B: Integer): Integer;  // Euclid
begin
  if B = 0 then Result := A
  else Result := GCD(B, A mod B);
end;

13.2 Towers of Hanoi

procedure Hanoi(N: Integer; Src, Dst, Via: Char);
begin
  if N = 0 then Exit;
  Hanoi(N - 1, Src, Via, Dst);
  Writeln('Move disk ', N, ' from ', Src, ' to ', Dst);
  Hanoi(N - 1, Via, Dst, Src);
end;

begin
  Hanoi(3, 'A', 'C', 'B');    // 7 moves
end.

13.3 Recursion vs iteration

Each call uses stack space (parameters, locals, return address). Deep recursion can overflow the stack (default 1 MB on Windows; FPC {$M} / -Cs sets the size; enable -Ct stack checking while debugging).

FPC and Delphi do not guarantee tail-call elimination — convert deep tail recursion to loops.

Memoize expensive recursive functions with an array or dictionary.

13.4 Nested routines

Routines can be declared inside other routines and can access the enclosing routine's parameters and locals:

Nested routines keep helpers private and avoid passing many parameters. They cannot be assigned to ordinary procedural variables (use is nested in FPC or anonymous methods in Delphi).

function CountWords(const S: string): Integer;
var
  I: Integer;

  function IsLetter(C: Char): Boolean;
  begin
    Result := C in ['A'..'Z', 'a'..'z', '0'..'9', ''''];
  end;

begin
  Result := 0;
  I := 1;
  while I <= Length(S) do
  begin
    while (I <= Length(S)) and not IsLetter(S[I]) do Inc(I);   // skip separators
    if I <= Length(S) then Inc(Result);
    while (I <= Length(S)) and IsLetter(S[I]) do Inc(I);       // skip the word
  end;
end;

13.5 Forward declarations

Pascal requires identifiers to be declared before use. For mutual recursion, declare the heading first with forward:

In units, routines declared in the interface section are implicitly forward-declared for the whole implementation section.

function IsOdd(N: Cardinal): Boolean; forward;

function IsEven(N: Cardinal): Boolean;
begin
  if N = 0 then Result := True
  else Result := IsOdd(N - 1);
end;

function IsOdd(N: Cardinal): Boolean;
begin
  if N = 0 then Result := False
  else Result := IsEven(N - 1);
end;

13.6 Example: recursive permutations

procedure Permute(S: string; L: Integer);
var
  I: Integer;
  T: Char;
begin
  if L = Length(S) then
    Writeln(S)
  else
    for I := L to Length(S) do
    begin
      T := S[L]; S[L] := S[I]; S[I] := T;   // S is a value parameter: a private copy
      Permute(S, L + 1);
    end;
end;

begin
  Permute('ABC', 1);   // ABC ACB BAC BCA CAB CBA
end.