SyntaxPilot
Courses/C Coding Questions/Lesson 22
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C Coding Questions · Lesson 22 of 30

Recursion questions I

factorial and sum of digits recursivelyfast power x^n (divide and conquer)base case and stack depth

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

  1. Base case: the smallest input, answered directly, with no call.
  2. 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 int holds 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) calls fact(-4), then fact(-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 with Segmentation 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 -s shows 8192 KB). Measured on this machine, print_up survived 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 is n / 10 (123). So sum(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 % M after 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

  1. 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).
  2. No overflow. half and x are always below M ≈ 10^9 (that's why main passes x % MOD), so half * half < 10^18 + … < 9.22 × 10^18, the long long maximum.

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

  1. What is recursion? A function that solves a problem by calling itself on a smaller instance, with a base case that stops it.
  2. 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.
  3. What is a stack frame? The memory a call uses on the stack: parameters, locals, the return address.
  4. What is a stack overflow? Using more stack than the limit (8 MB by default on Linux): Segmentation fault.
  5. 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).
  6. 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.
  7. Largest factorial that fits in an int, and in a long long? 12! and 20!.
  8. Why is fast power O(log n)? n halves at every step.
  9. Why take % M after every multiplication? To keep numbers below M² so they never overflow, and the final remainder is the same.
  10. What does -7 % 3 give 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.
  • int overflows at 13!; long long holds 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 a long 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.