Recursion in Delphi Grade 12

Recursion is when a function or procedure calls itself repeatedly until a base condition is met. It is a powerful technique for problems that can be broken down into smaller versions of the same problem.

What is Recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem, again and again, until the problem becomes so small it can be answered directly.

Analogy: picture a set of Russian nesting dolls. You open the biggest doll and find a smaller doll inside, open that and find a smaller one still, and you keep going until you reach the tiny doll that does not open. Recursion works the same way — each call opens up a slightly smaller version of the problem, and the smallest doll (the one that does not open) is the point where you stop.

A recursive routine is one that calls itself. Every recursive solution must have two parts:

Base case — the condition that stops the recursion (essential — without it you get infinite recursion)
Recursive case — the part where the function calls itself with a simpler input

Always have a base case

A recursive function without a base case will call itself forever, causing a stack overflow error and crashing the program.

Example 1 — Factorial

Factorial of n (written n!) = n × (n-1) × (n-2) × … × 1. Example: 5! = 5 × 4 × 3 × 2 × 1 = 120

Delphi — recursive factorial

function Factorial(n: Integer): Integer;
begin
  if n <= 1 then           // base case: factorial of 0 or 1 is 1
    Result := 1
  else                      // recursive case
    Result := n * Factorial(n - 1);
end;

// Calling it:
lblResult.Caption := IntToStr(Factorial(5));  // = 120

Trace — how Factorial(4) executes

Trace

Factorial(4)
  = 4 * Factorial(3)
      = 3 * Factorial(2)
          = 2 * Factorial(1)
              = 1        ← base case reached
          = 2 * 1 = 2
      = 3 * 2 = 6
  = 4 * 6 = 24

Example 2 — Sum of 1 to N

Delphi — recursive sum

function SumToN(n: Integer): Integer;
begin
  if n <= 0 then
    Result := 0           // base case
  else
    Result := n + SumToN(n - 1);  // recursive case
end;

// SumToN(4) = 4 + 3 + 2 + 1 + 0 = 10

Example 3 — Power (x to the power of n)

Delphi

function PowerOf(base, exp: Integer): Integer;
begin
  if exp = 0 then
    Result := 1                            // base case: x^0 = 1
  else
    Result := base * PowerOf(base, exp - 1); // recursive
end;

// PowerOf(2, 4) = 2*2*2*2 = 16

Example 4 — Fibonacci Sequence

Each number is the sum of the previous two: 0, 1, 1, 2, 3, 5, 8, 13…

Delphi

function Fibonacci(n: Integer): Integer;
begin
  if n <= 1 then
    Result := n                            // base cases: F(0)=0, F(1)=1
  else
    Result := Fibonacci(n - 1) + Fibonacci(n - 2);
end;

Recursion vs Iteration

	Recursion	Iteration (loop)
How it works	Function calls itself	Loop repeats a block
Code clarity	Often more elegant for naturally recursive problems	Usually easier to trace and debug
Memory use	Uses call stack (risk of stack overflow for large n)	Constant memory use
Speed	Can be slower due to function call overhead	Generally faster
Best for	Tree traversal, divide-and-conquer algorithms	Simple counting and totalling

Key Rules for Writing Recursive Functions

Always define a base case that returns a value without calling itself
Each recursive call must move toward the base case (e.g. decrease n by 1)
Test with small values first — trace through manually
Use a function (not procedure) so it can return a value

← PreviousCybercrime & Safeguards Next →Social Implications