Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 36 ยท Control Flow and Procedures

Recursion and Nested Routines in Pascal

Learn recursion in Pascal with factorial, Fibonacci and Towers of Hanoi, how the call stack works, base cases, nested procedures that share variables, and recursion versus loops.

A routine is recursive when it calls itself. Recursion feels odd at first, yet it is the natural way to express problems that contain smaller copies of themselves: a folder inside a folder, a tree whose branches are trees, a mathematical definition such as the factorial. Pascal supports recursion with no special keyword; you just call the routine by name inside its own body.

This lesson also covers nested routines: procedures declared inside other procedures, a classic Pascal feature that helps keep helper code private. Pascal code is read-only; the demos are C stand-ins.

Your first recursive function

The factorial of n is n * (n-1) * ... * 1, and 0! = 1. The definition refers to itself: n! = n * (n-1)!.

PASCAL
program Fact;

function Factorial(n: Integer): Int64;
begin
  if n <= 1 then
    Result := 1                     { base case }
  else
    Result := n * Factorial(n - 1); { recursive case }
end;

begin
  WriteLn(Factorial(5));            { 120 }
  WriteLn(Factorial(20));           { 2432902008176640000 }
end.

Every correct recursion has two parts:

  1. A base case that returns directly without calling itself. It stops the recursion.
  2. A recursive case that calls the routine with a smaller problem, moving toward the base case.

If you forget the base case, or the argument never gets smaller, the routine calls itself forever until the stack overflows and the program crashes.

The call stack

Each call gets its own set of parameters and local variables, stored in a stack frame. When Factorial(3) runs, it calls Factorial(2), which calls Factorial(1). Only then do the calls return, one by one, multiplying on the way back.

flowchart TD
    A["Factorial(3) waits"] --> B["Factorial(2) waits"]
    B --> C["Factorial(1) returns 1"]
    C --> D["Factorial(2) returns 2 * 1 = 2"]
    D --> E["Factorial(3) returns 3 * 2 = 6"]

Figure: calls pile up going down, results flow back up.

The stack has a fixed size (often 1 MB on Windows by default for the main thread, and a configurable limit for Free Pascal), so recursion depth of many thousands or millions is risky. For simple counting problems a loop is faster and uses no extra stack.

Fibonacci, and why naive recursion can be slow

PASCAL
function Fib(n: Integer): Int64;
begin
  if n < 2 then
    Result := n
  else
    Result := Fib(n - 1) + Fib(n - 2);
end;

This is correct and elegant, but each call spawns two more, so the number of calls grows exponentially: Fib(40) takes hundreds of millions of calls. An iterative version is far better:

PASCAL
function FibFast(n: Integer): Int64;
var
  a, b, t, i: Int64;
begin
  a := 0;
  b := 1;
  for i := 1 to n do
  begin
    t := a + b;
    a := b;
    b := t;
  end;
  Result := a;
end;

Another cure is to remember results already computed (memoization) in an array.

Towers of Hanoi

A famous puzzle: move n disks from peg A to peg C using peg B, never putting a larger disk on a smaller one. The recursive solution is short: move n-1 disks out of the way, move the biggest disk, then move the n-1 disks on top of it.

PASCAL
procedure Hanoi(n: Integer; from_, to_, via: Char);
begin
  if n = 0 then
    Exit;
  Hanoi(n - 1, from_, via, to_);
  WriteLn('Move disk ', n, ' from ', from_, ' to ', to_);
  Hanoi(n - 1, via, to_, from_);
end;

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

For n disks the number of moves is 2^n - 1, so 3 disks need 7 moves and 20 disks need 1,048,575.

Nested routines

Pascal lets you declare procedures and functions inside other routines. A nested routine can see the outer routine's parameters and local variables, but nothing outside can call it:

PASCAL
procedure PrintReport(const title: string; count: Integer);
var
  i: Integer;

  procedure Line;                 { nested: private helper }
  begin
    WriteLn(StringOfChar('=', Length(title)));
  end;

begin
  Line;
  WriteLn(title);
  Line;
  for i := 1 to count do
    WriteLn('Row ', i);
end;

Line can read title (the outer parameter) directly. The helper stays hidden, which keeps the program's global namespace clean. Nested routines are especially handy in recursive algorithms, where the outer routine holds the shared data and the nested one does the recursion:

PASCAL
function CountPaths(rows, cols: Integer): Int64;
var
  memo: array of array of Int64;

  function Walk(r, c: Integer): Int64;
  begin
    if (r = 0) or (c = 0) then
      Exit(1);
    if memo[r][c] = 0 then
      memo[r][c] := Walk(r - 1, c) + Walk(r, c - 1);
    Result := memo[r][c];
  end;

begin
  SetLength(memo, rows + 1, cols + 1);
  Result := Walk(rows, cols);
end;

Here memo is shared by every recursive call without being passed as a parameter. There is one restriction: a nested routine cannot normally be used as a callback via @ unless declared appropriately (Delphi's anonymous methods are the usual alternative).

Mutual recursion

Two routines can call each other when one has a forward declaration, as shown in Procedures and Functions. The even/odd pair there is a textbook example.

Recursion or loop?

Use recursion when Use a loop when
The problem is defined in terms of itself (trees, directories, divide and conquer) You simply repeat a step a known number of times
The depth is small and bounded The depth could be huge
Clarity matters more than speed Speed and memory matter

Stand-ins in C

The same recursive logic runs in C. These programs are C.

C C stand-in: factorial and Fibonacci

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

C C stand-in: Towers of Hanoi

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What are the two essential parts of a recursive routine?

    The base case stops the recursion; the recursive case must move toward it. Without both you get infinite recursion.
  2. 2. What happens if recursion never reaches its base case?

    Each call uses stack space. Unbounded recursion exhausts the stack, usually causing a crash.
  3. 3. Why is the naive recursive Fib(40) slow?

    The call tree grows exponentially. Iteration or memoization avoids the repeated work.
  4. 4. What can a nested procedure access?

    A nested routine sees the enclosing routine's variables, and itself is invisible outside it.

Summary

  • Recursion = a routine calling itself with a smaller problem, ending at a base case.
  • Each call uses stack space; very deep recursion can overflow the stack.
  • Naive Fibonacci is exponential; use iteration or memoization.
  • Nested routines are private helpers that share the outer routine's variables.

Next: Arrays: Static, Dynamic and Open