cint university / 101 / ced, the cint editor

101-11: functions that call themselves

This is lesson 101-11 of CU-101.2, checked against cint 0.2.0.

You will write a function that uses itself to get its answer. You will watch it reach the edge of I64 and read where the fault report says the call came from.

the program

The factorial of a number multiplies every whole number from 1 up to it: the factorial of 4 is 1 * 2 * 3 * 4, which is 24. Mathematicians write it as 4 followed by an exclamation mark. cint has no factorial sign, so in this program the mark is only text that the program prints.

I64 factorial(I64 n) {
    if (n <= 1) { return 1; }
    return n * factorial(n - 1);
}

void main() {
    for n in 1..=25 {
        "{n:>2}! = {factorial(n)}\n";
    }
}

Run this program in ced

Run it:

 1! = 1
 2! = 2
 3! = 6
 4! = 24
 5! = 120
 6! = 720
 7! = 5040
 8! = 40320
 9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
fault[E_OVERFLOW]: the exact result is outside the type's range
  --> factorial.ci:3:14
   |
 3 |     return n * factorial(n - 1);
   |              ^ mul.checked.i64
   |
   = operation: mul.checked.i64
   = operand-count: 2
   = operand: I64 21
   = operand: I64 2432902008176640000
   = exact:   51090942171709440000
   = limit:   I64 9223372036854775807
   = revision: c0baa23c76db8b75f2ee6e08b38a56964c2051f06b6e45554fefca759b36e4ba
   = source-map: none
   = address: none
   = stack-depth: 1
   = called from: factorial.ci:8:21
   = fuel-consumed: 253 (not part of the fault record)
   = state: the program stopped; stdout holds what it wrote before the fault

what happened

A function may call itself. The factorial of 4 is 4 times the factorial of 3, and the factorial of 3 is 3 times the factorial of 2. The second line of factorial says exactly that: the factorial of n is n times the factorial of n - 1. A function that calls itself is called recursive.

It needs a place to stop. if (n <= 1) { return 1; } answers the smallest case right away, without calling factorial again. Follow factorial(3):

1. factorial(3) needs 3 * factorial(2), so it calls factorial(2) and waits.
2. factorial(2) needs 2 * factorial(1), so it calls factorial(1) and waits.
3. factorial(1) returns 1 at once.
4. factorial(2) can now finish: 2 * 1 is 2.
5. factorial(3) can now finish: 3 * 2 is 6.

Factorials grow fast. The factorial of 20 is 2432902008176640000, which still fits in an I64. The factorial of 21 is 21 times that, 51090942171709440000, more than five times the largest I64. So the multiplication for 21 faulted, and the program printed 20 lines and stopped.

The report says where the call came from. --> factorial.ci:3:14 is where the fault happened: the * in factorial. called from: factorial.ci:8:21 is the line that called factorial: line 8, in main, at the factorial(n) in the print. The calls in progress at any moment are called the call stack. stack-depth: 1 counts the calls in progress besides main: here only factorial(21), the call that faulted. The calls for 20, 19 and the rest had already returned their answers.

change it

1. Make the loop stop at 20. Does the program finish now?
2. Write a recursive function sum_to(n) that adds 1 + 2 + ... + n, and print sum_to(100).
3. The largest U64 is 18446744073709551615, about twice the largest I64. Would the factorial of 21 fit in a U64? Work it out from the numbers in the report.

I64 sum_to(I64 n) {
    if (n == 0) { return 0; }
    return n + sum_to(n - 1);
}

when it goes wrong

Leave out the stopping line, and factorial calls itself for 5, 4, 3, 2, 1, 0, -1 and on without end:

I64 factorial(I64 n) {
    return n * factorial(n - 1);
}
void main() {
    "{factorial(5)}\n";
}

Run this program in ced

A program may have at most 256 calls in progress at once, and main counts as one of them. This program passes that limit and stops with a different fault:

fault[E_DEPTH]: call depth limit exceeded
  --> nobase.ci:2:16
   |
 2 |     return n * factorial(n - 1);
   |                ^ call.enter
   |
   = operation: call.enter
   = operand-count: 0
   = exact:   none
   = limit:   I64 256
   ...
   = stack-depth: 255

The full report lists 255 called from lines, one for each call in progress besides main. A recursive function needs a stopping case that every call eventually reaches.

new words

recursion, call stack

Next: lesson 101-12, lists.