Factorial (Recursive)

factorial(0) = 1, otherwise factorial(n) = n * factorial(n - 1). The smallest example of recursion with a single base case, used to visualise the call stack growing on descent and shrinking on unwind.

Algorithm

Basic Implementation

basic.dart

int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

void main() {
  final result = factorial(5);
  print(result);
}

The pinned run is factorial(5). The diagrams separate the descent, the base case, and the return values so the stack does not feel invisible.

Step 1 - Descend to the base case

Each call waits for one smaller call until f(0) returns 1.

Step 2 - Base value starts the unwind

The first finished frame is f(0) = 1; f(1) can now compute 1 * 1.

Step 3 - Unwind returns 120

Each frame multiplies its n by the completed smaller result.

Complexity

Time: O(n)
Space: O(n) call stack

Implementation notes

Dart: no need to grow the stack size at this depth; the standalone Dart VM handles n = 5 trivially.
The replay shows the call-stack contents on each frame and the computed n * factorial(n-1) value on each unwind, matching the lesson spec.

descend then unwind Each non-base call awaits the result of the next call, then multiplies.