These are the notes for C Coding Questions, episode 22, placement practice for people who finished the SyntaxPilot C course. Recursion questions, part one: factorial recursively (and why 13! breaks an int), how deep recursion can go before the stack overflows, the sum of digits recursively (and negative numbers), and fast power x^n modulo 1,000,000,007 by halving n (divide and conquer).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, glibc, Linux x86-64: 4-byte int, 8-byte long long, an 8 MB stack), the SyntaxPilot compiler's C command with warnings on, and every output below is real, with standard output going to a pipe as in the SyntaxPilot compiler. In the input lines below, ⏎ means pressing Enter.
Real-life pictures
| In real life | In C |
|---|---|
| in a cinema ticket queue, you ask the person ahead "what's your place?" and add one | recursion: a function that calls itself on a smaller copy of the problem |
| the person at the window knows the answer without asking: 1 | the base case: the smallest input, answered directly |
| everyone who asked is waiting, like plates piling up at a wedding buffet | the call stack: one stack frame per waiting call |
| too many plates and the pile topples | stack overflow: too many calls waiting, the program crashes |
| rice on a chessboard: the grains double on every square | powers grow fast, and halving shrinks them just as fast: fast power |
The idea: every recursive function has two parts
- Base case: the smallest input, answered directly, with no call.
- Recursive case: call the same function on a smaller input, then use that answer to finish the job.
For the queue: place(you) = place(person ahead) + 1, and place(front) = 1.
The rule that matters most: every call must move closer to the base case. If it doesn't, the calls never stop (and gcc may even warn you, see below).
A function with no base case at all:
#include <stdio.h>
int fact(int n) {
return n * fact(n - 1);
}
int main() {
printf("%d\n", fact(5));
return 0;
}
gcc warns at compile time:
main.c: In function 'fact':
main.c:3:5: warning: infinite recursion detected [-Winfinite-recursion]
3 | int fact(int n) {
| ^~~~
main.c:4:16: note: recursive call
4 | return n * fact(n - 1);
| ^~~~~~~~~~~
Q1: Factorial, recursively
Problem. Read numbers and print n! for each. n! ("n factorial") = 1 × 2 × 3 × … × n, and 0! = 1 by definition. Recursively: n! = n × (n − 1)!.
Think out loud.
0→ 1,5→ 120,12→ 479001600,13→ 6227020800.- Edge cases: 0; a negative number (factorial is not defined for it); 13 and above (does the answer still fit in the type?).
The obvious attempt: int, base case n == 0
#include <stdio.h>
int fact(int n) {
if (n == 0) return 1;
return n * fact(n - 1);
}
int main() {
int n;
while (scanf("%d", &n) == 1)
printf("%d! = %d\n", n, fact(n));
return 0;
}
Input 0 5 12 13⏎:
0! = 1
5! = 120
12! = 479001600
13! = 1932053504
13! is really 6,227,020,800. The program prints a wrong number, with no error.
Input -3⏎ (after about 4 seconds):
-3! = 0
Why it failed
- Overflow. An
intholds at most 2,147,483,647 (INT_MAX). 13! = 6,227,020,800 doesn't fit. Signed integer overflow is undefined behaviour (UB): the C standard makes no promise about the result. Here the value wrapped around. - A base case that is never reached.
fact(-3)callsfact(-4), thenfact(-5), … moving away from 0. With-O2, gcc turned the recursion into a loop, so it ran about four billion times (overflowing as it went, UB again) and printed garbage. Compiled without optimisation (gcc main.c), the same input crashes withSegmentation fault(stack overflow, see below). Both results are undefined behaviour: never rely on either.
The fix: long long, base case n <= 1, check the input first
long long holds up to 9,223,372,036,854,775,807, enough for 20! = 2,432,902,008,176,640,000, but not 21!.
#include <stdio.h>
long long fact(int n) {
if (n <= 1) return 1; /* base case: 0! = 1! = 1 */
return n * fact(n - 1); /* recursive case */
}
int main() {
int n;
while (scanf("%d", &n) == 1) {
if (n < 0)
printf("%d! : no factorial for negative numbers\n", n);
else if (n > 20)
printf("%d! : too big for long long\n", n);
else
printf("%d! = %lld\n", n, fact(n));
}
return 0;
}
Input 0 1 5 13 20 21 -3⏎:
0! = 1
1! = 1
5! = 120
13! = 6227020800
20! = 2432902008176640000
21! : too big for long long
-3! : no factorial for negative numbers
n * fact(n - 1): n is an int, the result of fact is a long long, so the multiplication is done in long long.
How the calls stack up
fact(4) = 4 × fact(3) waits
fact(3) = 3 × fact(2) waits
fact(2) = 2 × fact(1) waits
fact(1) = 1 base case
answers come back: 1 → 2 → 6 → 24
Each call that is waiting keeps a stack frame: a small block of stack memory with its own n and the place to return to. All the frames together are the call stack.
Complexity. n calls → O(n) time. At the deepest point n frames are waiting → O(n) stack space. Here n ≤ 20, so that's nothing.
A loop does the same in O(1) space:
#include <stdio.h>
int main() {
long long f = 1;
for (int i = 2; i <= 20; i++) f *= i;
printf("20! = %lld\n", f);
return 0;
}
20! = 2432902008176640000
Base case and stack depth: how deep is too deep?
print_up(n) prints 1 to n: first 1 to n − 1 (recursively), then n. The printf comes after the call, so every call must wait for the one below it.
#include <stdio.h>
void print_up(int n) {
if (n == 0) return; /* base case */
print_up(n - 1); /* first print 1 .. n-1 */
printf("%d\n", n); /* then n */
}
int main() {
int n;
scanf("%d", &n);
print_up(n);
return 0;
}
Input 5⏎:
1
2
3
4
5
Input 1000000⏎:
Segmentation fault
Nothing is printed at all.
Why
- A million calls are waiting at the same time → a million stack frames.
- The stack is 8 MB here (
ulimit -sshows 8192 KB). Measured on this machine,print_upsurvived about 700,000 calls deep and crashed beyond that. The exact limit depends on the machine, the compiler, the flags and the size of each frame, so never count on it. - Running out of stack is a stack overflow: the operating system kills the program with
Segmentation fault(signal SIGSEGV). Anything still in the output buffer (output to a pipe is buffered) is lost. - What matters is the depth (how many calls wait at once), not the total number of calls.
Fixes. Use a loop for simple counting, or design the recursion so the depth is small, like O(log n) in Q3. (gcc sometimes turns recursion into a loop by itself, as it did with fact at -O2: this is called tail-call or accumulator optimisation. Don't rely on it.)
Q2: Sum of digits, recursively
Problem. Print the sum of the digits of n, recursively. 1234 → 1 + 2 + 3 + 4 = 10.
Think out loud.
- The last digit is
n % 10(4); the rest isn / 10(123). Sosum(1234) = 4 + sum(123). - Base case: a single digit is its own sum (or: 0 has sum 0).
- Edge cases: 0; a single digit; a negative number like −472 (we want 13); the smallest
int.
The obvious attempt
#include <stdio.h>
int sum_digits(int n) {
if (n == 0) return 0;
return n % 10 + sum_digits(n / 10);
}
int main() {
int n;
while (scanf("%d", &n) == 1)
printf("sum_digits(%d) = %d\n", n, sum_digits(n));
return 0;
}
Input 1234 7 0 -472⏎:
sum_digits(1234) = 10
sum_digits(7) = 7
sum_digits(0) = 0
sum_digits(-472) = -13
Why it failed
In C (since C99), integer division rounds towards zero, and the remainder has the sign of the left operand:
-472 / 10 = -47 -472 % 10 = -2
-47 / 10 = -4 -47 % 10 = -7
-4 / 10 = 0 -4 % 10 = -4
So every digit comes out negative: −2 − 7 − 4 = −13.
The fix: flip the sign once, with a long long parameter
-n for the smallest int, −2,147,483,648, would be +2,147,483,648, which doesn't fit in an int (overflow, UB). In a long long it fits. The int argument is converted to long long when the function is called.
#include <stdio.h>
int sum_digits(long long n) {
if (n < 0) return sum_digits(-n); /* flip the sign once */
if (n < 10) return (int)n; /* base case: one digit */
return (int)(n % 10) + sum_digits(n / 10);
}
int main() {
int n;
while (scanf("%d", &n) == 1)
printf("sum_digits(%d) = %d\n", n, sum_digits(n));
return 0;
}
Input 1234 7 0 -472 2147483647 -2147483648⏎:
sum_digits(1234) = 10
sum_digits(7) = 7
sum_digits(0) = 0
sum_digits(-472) = 13
sum_digits(2147483647) = 46
sum_digits(-2147483648) = 47
Complexity. One call per digit: a number n has about log₁₀ n digits, so O(number of digits) = O(log n) time and stack depth (at most 11 calls for an int, including the sign flip).
Q3: Fast power, x^n modulo 1,000,000,007
Problem. Read pairs x n and print x^n modulo M = 1,000,000,007 (written 1e9+7). Powers grow huge, so contests and interviews ask for the answer modulo a big prime: the remainder after dividing by M.
Think out loud.
2 10→ 1024,3 5→ 243,7 0→ 1,2 1000000000→ 140625001,10 1000000000000000000→ 2401.- Modular arithmetic rule: (a × b) % M = ((a % M) × (b % M)) % M. So take
% Mafter every multiplication; the numbers never grow past M². - Edge cases: n = 0 (answer 1); n up to 10^18; x bigger than M (reduce it first).
The obvious attempt: x^n = x × x^(n−1)
#include <stdio.h>
#define MOD 1000000007
long long power(long long x, long long n) {
if (n == 0) return 1;
return x * power(x, n - 1) % MOD;
}
int main() {
long long x, n;
while (scanf("%lld %lld", &x, &n) == 2)
printf("%lld^%lld mod 1e9+7 = %lld\n", x, n, power(x, n));
return 0;
}
Input 2 10⏎3 5⏎:
2^10 mod 1e9+7 = 1024
3^5 mod 1e9+7 = 243
Input 2 1000000000⏎:
Segmentation fault
Why it failed
- n goes down by 1 per call, so 2^1,000,000,000 needs a billion calls waiting at once: far beyond the ~700,000 the stack allows. Stack overflow.
- Even as a loop, n = 10^18 would need 10^18 multiplications: at a billion per second, about 30 years.
The key insight: halve n (divide and conquer)
x^n = (x^(n/2))² if n is even
x^n = (x^(n/2))² × x if n is odd (n/2 rounds down)
2^10 = (2^5)², 2^5 = (2^2)² × 2, 2^2 = (2^1)², 2^1 = (2^0)² × 2, 2^0 = 1
Each call halves n, so there are about log₂ n + 2 calls: 31 for a billion, 61 for 10^18. This is divide and conquer: split into a half-size problem, solve it, combine. (It's also called binary exponentiation or exponentiation by squaring.)
The fix
#include <stdio.h>
#define MOD 1000000007
long long calls = 0;
long long power(long long x, long long n) {
calls++;
if (n == 0) return 1; /* base case: x^0 = 1 */
long long half = power(x, n / 2); /* ONE call for half */
long long result = half * half % MOD;
if (n % 2 == 1) result = result * x % MOD; /* odd n: one more x */
return result;
}
int main() {
long long x, n;
while (scanf("%lld %lld", &x, &n) == 2) {
calls = 0;
long long p = power(x % MOD, n);
printf("%lld^%lld mod 1e9+7 = %lld, calls = %lld\n", x, n, p, calls);
}
return 0;
}
Input:
2 10
3 5
7 0
2 1000000000
10 1000000000000000000
123456789012 2
Output:
2^10 mod 1e9+7 = 1024, calls = 5
3^5 mod 1e9+7 = 243, calls = 4
7^0 mod 1e9+7 = 1, calls = 1
2^1000000000 mod 1e9+7 = 140625001, calls = 31
10^1000000000000000000 mod 1e9+7 = 2401, calls = 61
123456789012^2 mod 1e9+7 = 433410910, calls = 3
Every answer was checked against Python's pow(x, n, 1000000007).
Two details that matter
- Call once and store it.
power(x, n / 2) * power(x, n / 2)looks the same, but makes two calls per level: 1 + 2 + 4 + … ≈ 2n calls in total, back to O(n) time (the depth stays log n, so it no longer crashes, it's just slow). - No overflow.
halfandxare always below M ≈ 10^9 (that's whymainpassesx % MOD), sohalf * half< 10^18 + … < 9.22 × 10^18, thelong longmaximum.
Complexity. O(log n) time and O(log n) stack depth: 61 frames for n = 10^18.
The same idea as a loop (O(1) space), reading the bits of n from the lowest:
#include <stdio.h>
#define MOD 1000000007
long long power(long long x, long long n) { /* iterative fast power */
long long result = 1;
x %= MOD;
while (n > 0) {
if (n % 2 == 1) result = result * x % MOD;
x = x * x % MOD;
n /= 2;
}
return result;
}
int main() {
printf("%lld\n", power(2, 1000000000));
printf("%lld\n", power(10, 1000000000000000000LL));
return 0;
}
140625001
2401
Complexity summary
| Task | Method | Time | Stack space | Note |
|---|---|---|---|---|
| factorial | recursion | O(n) | O(n) | n ≤ 20 for long long |
| factorial | loop | O(n) | O(1) | |
| print 1..n | recursion, print after the call | O(n) | O(n) | crashed at 1,000,000 |
| sum of digits | recursion | O(digits) = O(log n) | O(log n) | ≤ 11 calls for an int |
| x^n mod M | x × x^(n−1) | O(n) | O(n) | crashed at 10^9 |
| x^n mod M | halving, one call stored | O(log n) | O(log n) | 61 calls for 10^18 |
| x^n mod M | halving, two calls | O(n) | O(log n) | the speedup is lost |
| x^n mod M | iterative halving | O(log n) | O(1) |
Common mistakes (and the real results)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| no base case | warning: infinite recursion detected [-Winfinite-recursion] |
the calls never stop | answer the smallest input directly |
fact(-3) with base case n == 0 |
-3! = 0 after 4 s (at -O0: Segmentation fault) |
moves away from the base case; overflow (UB) | check n < 0 first; base case n <= 1 |
int fact(13) |
13! = 1932053504 |
signed overflow (UB) | long long, refuse n > 20 |
| recursion a million deep | Segmentation fault, no output |
stack overflow (8 MB) | a loop, or O(log n) depth |
sum_digits(-472) |
-13 |
% keeps the sign |
recurse on -n once |
-n for INT_MIN in an int |
overflow (UB) | +2,147,483,648 doesn't fit | long long parameter |
x * power(x, n - 1) for big n |
Segmentation fault |
n frames | halve n |
power(x, n/2) * power(x, n/2) |
no error, O(n) calls | the same work twice | store it in half |
x * y % MOD with x, y up to 10^12 |
wrong answers (overflow, UB) | the product passes 9.2 × 10^18 | reduce x % MOD first |
Your turn: digital root (solution)
Problem. Keep adding the digits of n until one digit is left. 9875 → 29 → 11 → 2; 7 → 7; 999999999999 → 108 → 9 → 9. Handle negative numbers (use the absolute value).
Idea. If n has one digit, that's the answer; otherwise it's the digital root of the digit sum. Reuse Q2. Each step makes the number much smaller (a 12-digit number becomes at most 108), so there are very few steps: about O(digits) time.
Show the solution
#include <stdio.h>
int digit_sum(long long n) {
if (n < 10) return (int)n;
return (int)(n % 10) + digit_sum(n / 10);
}
int digital_root(long long n) {
if (n < 0) n = -n;
if (n < 10) return (int)n; /* one digit: done */
return digital_root(digit_sum(n)); /* sum the digits, then again */
}
int main() {
long long n;
while (scanf("%lld", &n) == 1)
printf("digital_root(%lld) = %d\n", n, digital_root(n));
return 0;
}
Input 9875 7 0 -472 999999999999⏎:
digital_root(9875) = 2
digital_root(7) = 7
digital_root(0) = 0
digital_root(-472) = 4
digital_root(999999999999) = 9
(There's also an O(1) formula: for n > 0, the digital root is 1 + (n − 1) % 9.)
Practice questions (with solutions)
1. Count the digits of n recursively.
Solution
#include <stdio.h>
int count_digits(long long n) {
if (n < 0) return count_digits(-n);
if (n < 10) return 1; /* 0..9: one digit */
return 1 + count_digits(n / 10);
}
int main() {
long long n;
while (scanf("%lld", &n) == 1)
printf("count_digits(%lld) = %d\n", n, count_digits(n));
return 0;
}
Input 0 7 1234 -472 1000000000000⏎:
count_digits(0) = 1
count_digits(7) = 1
count_digits(1234) = 4
count_digits(-472) = 3
count_digits(1000000000000) = 13
Note the base case n < 10 makes 0 count as one digit; a base case n == 0 → 0 would say 0 has zero digits.
2. Print n down to 1 and back up, with one recursive function. 4 → 4 3 2 1 1 2 3 4.
Solution
Print before the call (on the way down) and again after it (on the way back up).
#include <stdio.h>
void down_up(int n) {
if (n == 0) return;
printf("%d ", n); /* on the way down */
down_up(n - 1);
printf("%d ", n); /* on the way back up */
}
int main() {
down_up(4);
printf("\n");
return 0;
}
4 3 2 1 1 2 3 4
3. x^n for a negative n, with doubles. x^−n = 1 / x^n.
Solution
#include <stdio.h>
double power(double x, long long n) {
if (n < 0) return 1.0 / power(x, -n); /* x^-n = 1 / x^n */
if (n == 0) return 1.0;
double half = power(x, n / 2);
return (n % 2 == 0) ? half * half : half * half * x;
}
int main() {
printf("%g\n", power(2, 10));
printf("%g\n", power(2, -3));
printf("%g\n", power(1.5, 2));
printf("%g\n", power(10, -2));
return 0;
}
1024
0.125
2.25
0.01
(0 to a negative power divides by zero: with doubles that gives inf, so check x = 0 if your problem allows it.)
4. Dry run: what is the recursion depth of sum_digits(-2147483648)?
Answer
1 call for the sign flip, then one per digit until a single digit is left: 2147483648 (10 digits) → 9 more calls → the last call sees 2. 11 calls in total, so the depth is 11.
Quick quiz
#include <stdio.h>
int f(int n) {
if (n <= 0) return 0;
return n + f(n - 2);
}
int main() {
printf("%d\n", f(7));
return 0;
}
What does it print? (A) 16 (B) 28 (C) 12 (D) It never stops
Answer
(A) 16. f(7) = 7 + f(5) = 7 + 5 + f(3) = 7 + 5 + 3 + f(1) = 7 + 5 + 3 + 1 + f(−1), and f(−1) hits the base case n <= 0 and returns 0. Real output: 16. With a base case n == 0 instead, the odd numbers would jump from 1 to −1 and never reach it.
Interview questions
- What is recursion? A function that solves a problem by calling itself on a smaller instance, with a base case that stops it.
- What happens without a base case? The calls never end: a stack overflow (crash), or an endless loop if the compiler turned it into one. gcc warns with
-Winfinite-recursion. - What is a stack frame? The memory a call uses on the stack: parameters, locals, the return address.
- What is a stack overflow? Using more stack than the limit (8 MB by default on Linux):
Segmentation fault. - Recursion or a loop for factorial? A loop: same O(n) time, O(1) space. Recursion is clearer for problems that split naturally (trees, divide and conquer).
- What is tail recursion? The recursive call is the very last thing the function does; compilers can turn it into a loop (tail-call optimisation). C doesn't guarantee it.
- Largest factorial that fits in an
int, and in along long? 12! and 20!. - Why is fast power O(log n)? n halves at every step.
- Why take
% Mafter every multiplication? To keep numbers below M² so they never overflow, and the final remainder is the same. - What does
-7 % 3give in C? −1 (the remainder has the sign of the left operand).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Recursion | A function that calls itself on a smaller input | fact(n) calls fact(n - 1) |
| Base case | The smallest input, answered without a recursive call | if (n <= 1) return 1; |
| Recursive case | The part that calls the function on a smaller input | return n * fact(n - 1); |
| Factorial (n!) | 1 × 2 × … × n; 0! = 1 | 5! = 120 |
| Integer overflow | A result too big for its type | 13! in an int |
INT_MAX |
The largest int: 2,147,483,647 |
from <limits.h> |
INT_MIN |
The smallest int: −2,147,483,648 |
-INT_MIN overflows |
| Undefined behaviour (UB) | The C standard makes no promise about the result | signed overflow |
long long |
A 64-bit integer, up to about 9.22 × 10^18 | long long fact(int n) |
| Stack frame | One call's block of stack memory | fact's n and return address |
| Call stack | All the frames of the calls waiting right now | fact(4) → fact(3) → … |
| Recursion depth | How many calls wait at the same time | 1,000,000 for print_up(1000000) |
| Stack overflow | More stack used than there is: a crash | Segmentation fault |
| Segmentation fault | The OS stopped the program for touching memory it may not use (SIGSEGV) | deep recursion |
-Winfinite-recursion |
gcc warning for recursion that can never stop | fact with no base case |
| Tail-call optimisation | The compiler turns a recursive call into a jump/loop | gcc -O2 on fact |
% (remainder) |
What's left after integer division; keeps the left operand's sign | -472 % 10 = -2 |
| Truncation towards zero | How C rounds integer division | -472 / 10 = -47 |
| Modulo M | The remainder after dividing by M | x % 1000000007 |
| 1e9+7 | The prime 1,000,000,007, a common modulus | #define MOD 1000000007 |
| Divide and conquer | Split into smaller problems, solve, combine | x^n from x^(n/2) |
| Fast power / binary exponentiation | Computing x^n in O(log n) multiplications | power(x, n / 2) |
| O(log n) | Work that grows with the number of halvings of n | 61 calls for 10^18 |
| Digital root | Repeated digit sum until one digit is left | 9875 → 2 |
Summary
- A recursive function needs a base case and a recursive case that moves towards it. If the input can step past the base case (negative numbers), check it first.
intoverflows at 13!;long longholds up to 20!. Overflow of signed integers is undefined behaviour.- Every waiting call is a stack frame; the depth decides the stack used. About 700,000 calls deep crashed here (8 MB stack): use a loop or a shallow recursion.
%and/round towards zero, so digits of a negative number come out negative: flip the sign once (in along long).- Fast power halves n each call: O(log n) time and depth. Call once and store
half, and reduce modulo M after every multiplication.
Next episode: Recursion questions II: the Tower of Hanoi (moves = 2^n − 1), all permutations of a string, and recursive binary search.