A greatest-common-divisor call
Call gcd2(18, 30). It replaces the pair with (30 % 18, 18), giving (12, 18), then (6, 12), then (0, 6). At zero, it returns 6. Each call solves the same problem with smaller arguments. section 7.3
8 size_t gcd2(size_t a, size_t b) {
9 assert(a <= b);
10 if (!a) return b;
11 size_t rem = b % a;
12 return gcd2(rem, a);
13 }
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":0,\"ch\":1},{\"line\":0,\"ch\":2}],[{\"line\":0,\"ch\":5},{\"line\":0,\"ch\":11}],[{\"line\":3,\"ch\":7},{\"line\":3,\"ch\":13}],[{\"line\":0,\"ch\":5},{\"line\":0,\"ch\":11}],[{\"line\":3,\"ch\":7},{\"line\":3,\"ch\":13}],[{\"line\":0,\"ch\":5},{\"line\":0,\"ch\":11}],[{\"line\":3,\"ch\":7},{\"line\":3,\"ch\":13}],[{\"line\":1,\"ch\":1},{\"line\":1,\"ch\":2}],[{\"line\":1,\"ch\":7},{\"line\":1,\"ch\":13}],[{\"line\":2,\"ch\":0},{\"line\":2,\"ch\":2}],[{\"line\":2,\"ch\":7},{\"line\":2,\"ch\":9}],[{\"line\":2,\"ch\":15},{\"line\":2,\"ch\":21}],[{\"line\":4,\"ch\":7},{\"line\":4,\"ch\":13}],[{\"line\":3,\"ch\":0},{\"line\":3,\"ch\":2}],[{\"line\":0,\"ch\":5},{\"line\":0,\"ch\":11}],[{\"line\":3,\"ch\":7},{\"line\":3,\"ch\":13}],[{\"line\":4,\"ch\":0},{\"line\":4,\"ch\":2}],[{\"line\":2,\"ch\":15},{\"line\":2,\"ch\":21}],[{\"line\":4,\"ch\":7},{\"line\":4,\"ch\":13}],[{\"line\":5,\"ch\":0},{\"line\":5,\"ch\":2}]]"}
!@%STYLE%@!
The zero test returns the answer before the modulus operation. Otherwise, the remainder becomes the first argument of another gcd2 call; the assertion checks the required argument order. section 7.3
A function that calls itself, directly or indirectly, is recursive; the technique is recursion. Every call gets newly initialized parameters and local variables, even while an earlier call to that function is still active. TAKEAWAY: recursive calls have distinct local instances, not one set of locals reused by every call. section 7.3 section 13.2.2
The gcd2 example has two essential parts: a case that returns without another call, and a step that preserves the answer while reducing the problem. Its public-facing gcd function first checks that both inputs are nonzero and puts them in the order gcd2 expects. section 7.3
4 size_t fib(size_t n) {
5 if (n < 3)
6 return 1;
7 else
8 return fib(n-1) + fib(n-2);
9 }
!@%STYLE%@!
{"css":"{\"css\": \"font-weight: bold;\"}","target":"[[{\"line\":0,\"ch\":0},{\"line\":0,\"ch\":1}],[{\"line\":0,\"ch\":4},{\"line\":0,\"ch\":10}],[{\"line\":0,\"ch\":4},{\"line\":0,\"ch\":10}],[{\"line\":1,\"ch\":0},{\"line\":1,\"ch\":1}],[{\"line\":1,\"ch\":6},{\"line\":1,\"ch\":8}],[{\"line\":2,\"ch\":0},{\"line\":2,\"ch\":1}],[{\"line\":2,\"ch\":8},{\"line\":2,\"ch\":14}],[{\"line\":4,\"ch\":8},{\"line\":4,\"ch\":14}],[{\"line\":3,\"ch\":0},{\"line\":3,\"ch\":1}],[{\"line\":3,\"ch\":6},{\"line\":3,\"ch\":10}],[{\"line\":4,\"ch\":0},{\"line\":4,\"ch\":1}],[{\"line\":2,\"ch\":8},{\"line\":2,\"ch\":14}],[{\"line\":4,\"ch\":8},{\"line\":4,\"ch\":14}],[{\"line\":5,\"ch\":0},{\"line\":5,\"ch\":1}]]"}
!@%STYLE%@!
Fibonacci takes a different shape: for n of at least 3, one call starts two more calls and adds their results; smaller inputs return 1. section 7.3
Two calls can repeat work: evaluating fib(5) reaches fib(3) both directly and through fib(4). One alternative keeps previously computed values in a cache passed to recursive calls. Another passes a two-element result buffer and updates it on each call. These are different ways to carry information through recursion. section 7.3
Distinct local variables do not guarantee independent state. Recursive calls that receive pointers can modify the same pointed-to data. A recursive-descent parser uses this pattern while following nested braces; its shared depth pointer makes the state harder to follow than a depth value passed as an argument. TAKEAWAY: distinguish each call’s local pointer from the object it points to. section 17.1 section 17.4
