A recursive routine must always contain:

a base case. The base case is what allows the recursion to stop. Without it the calls never end.

A recursive function with no base case will:

cause a stack overflow. Every call pushes a frame and none ever returns, so the stack memory is exhausted.

A stack frame stores:

the return address, parameters and local variables. It holds everything needed to resume the suspended call once the deeper one returns.

For F(n) = n × F(n−1) with F(1) = 1, calling F(4) pushes how many frames?

4. Frames are pushed for F(4), F(3), F(2) and F(1) — four in total. 24 is the result, not the depth.

During recursion, calculations happen:

on the way back up after the base case. Each call is suspended at the recursive call. The work is completed as the frames are popped.

Recursive calls complete in which order?

last in, first out. The stack is LIFO, so the most recently pushed frame is the first to be popped and completed.

The main disadvantage of recursion compared with iteration is:

it uses more memory for stack frames. Anything recursive can be written iteratively; the cost is one stack frame per level of depth.

Recursion is most naturally suited to:

traversing a tree. A tree is itself defined recursively, so a recursive traversal matches the structure. Simple repetition is better served by a loop.

Recursion — Computer Science Notes, Worked Examples and Quiz

Defining something in terms of itself

A recursive routine is one that calls itself. That sounds circular, and it would be, except for one requirement: every recursive definition must contain a base case — a situation it can answer directly without calling itself again.

Each call must also move towards that base case. Together these two conditions guarantee the process terminates. Remove either and the routine calls itself forever, which in practice means the call stack fills and the program crashes with a stack overflow.

Both conditions are examined. "It must have a base case" earns half the marks; the other half is for the progress towards it.

every recursive routine needs:1. a BASE CASE that returns without recursing2. a RECURSIVE CASE that moves towards itfactorial:F(1) = 1base caseF(n) = n × F(n − 1)recursive casewithout a base case the recursion never stops

base case: the stopping conditionanswered directly, with no further call
recursive case: the self-callmust use a smaller or simpler argument
stack overflow: the failure modewhat happens when it never terminates

Recursion is easiest to follow as a trace: each call is pushed and waits, and nothing is computed on the way down. The answers are built on the way back up, once the base case has been reached.

The stack is what makes it work

When a routine calls another, the computer must remember where to come back to. It pushes a stack frame holding the return address, the parameters and the local variables. When the call finishes, the frame is popped and execution resumes.

Recursion uses exactly the same mechanism, just with the routine calling itself. Computing F(4) pushes frames for 4, 3, 2 and 1. Nothing is calculated on the way down — each call is suspended waiting on the next. Only when the base case returns does the answer travel back up, each frame completing its multiplication as it is popped.

This is why deep recursion is expensive: every level costs a frame of memory, and there is a limit. It is also why the stack is a last in, first out structure — the most recent call must finish first.

Worked example

Trace the calls and returns for the recursive factorial function F(n) = n × F(n−1), with F(1) = 1, when called as F(4).

F(4) is called. It cannot return yet — it needs F(3). A frame is pushed.The multiplication 4 × F(3) cannot happen until F(3) is known.
F(3) calls F(2), which calls F(1). Four frames are now on the stack.Each call suspends and waits. Nothing has been calculated yet.
F(1) = 1 — the base case returns directly without recursing.This is what stops the descent and starts the unwinding.
F(2) = 2 × 1 = 2, and its frame is popped.Now that F(1) has returned, F(2) can complete its multiplication.
F(3) = 3 × 2 = 6, then F(4) = 4 × 6 = 24.Each frame completes in reverse order of calling — last in, first out.

F(4) = 24, with four frames pushed and popped in reverse order

Nothing is computed on the way down

A common misunderstanding is that each call does part of the work as it descends. It does not — every call is suspended at the point of the recursive call, waiting. All the arithmetic happens during the return journey, after the base case. Tracing questions are marked on exactly this ordering.

Recursion or iteration?

Anything expressible recursively can be written iteratively and vice versa, so the choice is about clarity and cost rather than capability.

Recursion is far more readable when the problem itself is recursive — walking a tree, traversing a directory of directories, or a divide-and-conquer algorithm such as quicksort or binary search. Iteration is more efficient for simple repetition, because it uses no stack frames.

	Recursion	Iteration
Memory	a stack frame per call	constant
Speed	slower — call overhead	faster
Risk	stack overflow if too deep	infinite loop, but no crash
Readability	excellent for recursive structures	better for simple repetition
Typical use	trees, quicksort, binary search	counting, summing, scanning a list

What to say in an exam

Every recursive routine needs a base case and progress towards it.
Without both, the stack fills and the program crashes with a stack overflow.
Each call pushes a frame holding the return address, parameters and locals.
The stack is LIFO, so the most recent call completes first.
Nothing is computed on the way down; the work happens on the way back.
Recursion suits recursive data structures; iteration is cheaper for plain repetition.

Converting between recursion and iteration

Because both can express any computation, questions often ask for one rewritten as the other. The conversion is mechanical once the structure is recognised.

Turning recursion into iteration means replacing the implicit stack with an explicit loop. For a simple accumulating recursion such as factorial, a single loop with a running total is enough, because there is nothing to remember beyond that total. For a branching recursion such as a tree traversal, the stack must be recreated explicitly with a stack data structure — which is precisely why recursion is preferred there.

Turning iteration into recursion means making the loop variable a parameter and the loop's exit condition the base case. What the loop body accumulated becomes what the recursive call returns.

RECURSIVEITERATIVEFUNCTION Fact(n)FUNCTION Fact(n)IF n = 1 THENtotal ← 1RETURN 1FOR i ← 2 TO nELSEtotal ← total × iRETURN n * Fact(n-1)NEXT iENDIFRETURN totalENDFUNCTIONENDFUNCTIONsame result; the loop needs no stack framesthe base case becomes the loop initialisation and exit condition

base case: becomesthe starting value and the loop bound
recursive call: becomesthe next iteration of the loop
stack frames: becomea single accumulating variable

When the conversion is not worth doing

For factorial the iterative version is plainly better — same result, no stack cost. For a tree traversal the iterative version needs an explicit stack that the programmer has to push and pop by hand, which is longer, harder to read and easier to get wrong than simply letting the language's own call stack do the job. The right answer to "should this be rewritten iteratively" depends entirely on whether the problem is itself recursive.

Recursion