Functions and Records

Recursion

Base Case and Unwinding

A recursive function calls itself with a smaller input. The base case stops the recursion; the recursive case combines the current value with the result of the next call. Each return resolves one frame on the way back out.

Program

Play the program to compute factorial(4) and watch the calls descend to the base case and unwind.

recursion.dart
Replay: real traced execution (multi-file project)
int factorial(int n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

void main() {
  var result = factorial(4);
  print(result);
}

  1. call ← factorial(4)

    6void main() {7  var result = factorial(4);8  print(result);
    values this stepfactorial(4)call

  2. return value ← waiting for factorial(3)

    2  if (n <= 1) return 1;3  return n * factorial(n - 1);4}
    values this stepwaiting for factorial(3)return value4n

  3. return value ← waiting for factorial(2)

    2  if (n <= 1) return 1;3  return n * factorial(n - 1);4}
    values this stepwaiting for factorial(2)return value3n

  4. return value ← waiting for factorial(1)

    2  if (n <= 1) return 1;3  return n * factorial(n - 1);4}
    values this stepwaiting for factorial(1)return value2n

  5. base case ← return 1

    1int factorial(int n) {2  if (n <= 1) return 1;3  return n * factorial(n - 1);
    values this stepreturn 1base case1n

  6. return value ← 2 * 1 = 2

    2  if (n <= 1) return 1;3  return n * factorial(n - 1);4}
    values this step2 * 1 = 2return value2n

  7. return value ← 3 * 2 = 6

    2  if (n <= 1) return 1;3  return n * factorial(n - 1);4}
    values this step3 * 2 = 6return value3n

  8. return value ← 4 * 6 = 24

    2  if (n <= 1) return 1;3  return n * factorial(n - 1);4}
    values this step4 * 6 = 24return value4n

  9. result ← 24

    6void main() {7  var result = factorial(4);8  print(result);
    values this step24result

  10. print(result);

    7  var result = factorial(4);8  print(result);9}
    output24
    values this step24result
base case `if (n <= 1) return 1;` stops the recursion; without it the calls would never end.
recursive case `n * factorial(n - 1)` calls the same function with a smaller argument.
unwinding Each return resolves one frame: `factorial(2) = 2*1 = 2`, then `factorial(3) = 3*2 = 6`, then `factorial(4) = 4*6 = 24`.