AlgoScope

Recursion to Iteration

A tail call is a loop in disguise: replace the call with an update of the arguments and jump back.

Recursion, analysis, intermediate
Tail call with n 4 and acc 5, depth still 1.factTail(4, 5)bottomtop

The Call Stack: Tail recursion reuses the frame

Decision, step 2 of 8

factTail(5, 1) calls factTail(4, 1 x 5 = 5) and has nothing to do with the result but pass it on. The frame is reused: same slot, new arguments.

How the call stack works

Cost

Space
O(depth)

Taught by the same lesson

The Call Stack covers these too, in the same run.