Functions That Call Themselves
Recursion is when a function or procedure calls itself, directly or indirectly, to solve a problem by breaking it into smaller instances of the same problem. Every correct recursive subprogram needs two essential parts: a base case that stops the recursion by returning a result without any further self-call, and a recursive case that reduces the problem and calls itself again, always moving closer to the base case.
Cricket analogy: A run-chase commentary that recalculates the required run rate after every single ball is a recursive process — each call depends on a smaller version of the same problem, fewer balls, adjusted target, until the base case of zero balls remaining is reached.
Writing a Correct Recursive Function
Each recursive call creates its own stack frame holding that call's local variables and parameters, completely separate from every other active call's frame, which is precisely how a recursive function can track different states — like the countdown value in a factorial calculation — at each level simultaneously. If the recursive case never actually moves the problem closer to the base case, for example calling itself with the same or a larger argument, the recursion never terminates and the program eventually exhausts the call stack.
Cricket analogy: Each nested video review during a match keeps its own separate replay footage and angle, just as each recursive call has its own stack frame holding that call's specific local state, independent of the others.
function Factorial(n: Integer): Integer;
begin
if n <= 1 then
Factorial := 1 { base case }
else
Factorial := n * Factorial(n - 1); { recursive case }
end;Recursion vs Iteration
Recursive solutions often express an algorithm's structure more directly than an equivalent loop — a tree traversal or the Tower of Hanoi reads far more naturally as recursion than as an explicit stack-managed loop — but that clarity comes at the cost of stack space: every call adds a frame, and standard Pascal implementations do not guarantee tail-call optimization, so even a recursive function written in a tail-recursive style still consumes one stack frame per call rather than being converted into a loop by the compiler.
Cricket analogy: Describing a partnership's building as 'this over's runs plus the rest of the partnership' reads more naturally than a manually tracked running tally, but a very long partnership tracked this way still needs a record of every over's context kept somewhere, just as unoptimized recursion keeps a frame per call.
Deep or unbounded recursion can exhaust the call stack and crash the program with a stack overflow — always verify that your base case is reachable for every valid input, and consider an iterative rewrite for algorithms that may recurse thousands of levels deep.
Mutual and Indirect Recursion
Mutual recursion occurs when two subprograms call each other rather than a single function calling itself directly — for example, an IsEven function that calls IsOdd, which in turn calls IsEven with a smaller argument. As covered when discussing procedures and functions, Pascal's single-pass compilation means the first of the pair must be declared with the forward directive so the compiler recognizes its partner's identifier before the partner's full definition appears in the source.
Cricket analogy: A bowling pair operating a 'good cop, bad cop' spell where the pacer's aggressive over sets up conditions for the spinner's next over, which in turn sets up the pacer's following over, is mutual recursion between two distinct roles, each depending on the other's prior work.
function IsOdd(n: Integer): Boolean; forward;
function IsEven(n: Integer): Boolean;
begin
if n = 0 then
IsEven := True
else
IsEven := IsOdd(n - 1);
end;
function IsOdd(n: Integer): Boolean;
begin
if n = 0 then
IsOdd := False
else
IsOdd := IsEven(n - 1);
end;Mutual recursion is a natural fit for state-machine-like problems — such as parsers that alternate between two grammar rules — but always confirm both functions still converge toward their base cases as arguments shrink, or the mutual calls will recurse forever just like a single self-recursive function without progress.
- Every correct recursive subprogram needs a base case and a recursive case that shrinks the problem
- Each recursive call gets its own independent stack frame holding that call's local state
- Recursion without a reachable base case causes infinite recursion and eventually a stack overflow
- Standard Pascal does not guarantee tail-call optimization, so deep recursion always consumes stack space
- Recursive solutions often mirror a problem's natural structure more clearly than iterative ones
- Mutual recursion is when two subprograms call each other rather than a function calling itself
- Mutually recursive functions require a forward declaration for the first one declared
Practice what you learned
1. What are the two essential parts of any correct recursive function?
2. What happens if a recursive function's base case is never reached for some input?
3. Does standard Pascal guarantee tail-call optimization for recursive functions?
4. What is required to implement mutual recursion between two functions in Pascal?
5. Each recursive call maintains its own...
Was this page helpful?
You May Also Like
Procedures and Functions
Learn how Pascal separates reusable code into procedures (no return value) and functions (return a value), and how to declare and call each.
Parameters and Scope
Understand Pascal's value vs var parameters and how block-structured scoping controls variable visibility.
Loops in Pascal
Master Pascal's three loop constructs — for, while, and repeat-until — and know when to use each.
Related Reading
Related Study Notes in Programming
Browse all study notesApache Spark Study Notes
Programming · 30 topics
ProgrammingApache Flink Study Notes
Programming · 30 topics
ProgrammingHadoop Study Notes
Programming · 30 topics
ProgrammingSnowflake Study Notes
Programming · 30 topics
ProgrammingApache Airflow Study Notes
Programming · 30 topics
Programmingdbt (Data Build Tool) Study Notes
Programming · 30 topics