What is Recursion?
Recursion means a function that calls itself. Instead of solving the whole problem at once, it breaks it down into a smaller version of the same problem — then calls itself on that smaller version.
Think of it like looking up a word in a dictionary. The definition uses another word you don't know. So you look that one up too. And that definition uses another word… until finally you reach a word you already know. That "word you already know" is the base case — the stopping point.
Every recursive function has exactly two parts:
- Base case — the stopping condition. When this is true, the function returns a simple value and stops calling itself.
- Recursive case — calls itself with a smaller input, getting closer to the base case each time.
stack overflow. The base case is not optional.The sum() Function — Adding 1 to 10
The problem: add all numbers from 1 to m. So sum(5) = 1+2+3+4+5 = 15.
The recursive insight: sum(5) = 5 + sum(4). You don't need to know the answer to sum(4) right now — just ask for it! The function handles the rest.
sum(5) = 5 + sum(4) sum(4) = 4 + sum(3) sum(3) = 3 + sum(2) sum(2) = 2 + sum(1) sum(1) = 1 + sum(0) sum(0) = 0 ← BASE CASE — stop here
#include <stdio.h> /* Prototype — tell compiler sum() exists before main uses it */ int sum(int m); int main() { int result = sum(10); /* add 1+2+3+...+10 */ printf("Sum 1 to 10 = %d\n", result); /* 55 */ printf("Sum 1 to 5 = %d\n", sum(5)); /* 15 */ printf("Sum 1 to 3 = %d\n", sum(3)); /* 6 */ return 0; } int sum(int m) { if (m > 0) { return m + sum(m - 1); /* recursive case: call with smaller m */ } else { return 0; /* base case: m is 0, stop here */ } }
Sum 1 to 10 = 55 Sum 1 to 5 = 15 Sum 1 to 3 = 6
Step by Step — How sum(5) Actually Runs
When you call sum(5), the function doesn't immediately know the answer. It asks sum(4), which asks sum(3)... all the way down to sum(0). Then the answers travel back up, adding one number at a time.
There are two phases: going DOWN (building up calls) and coming back UP (collecting answers).
Phase 1 — going down (each call waits for the next)
Phase 2 — coming back up (answers travel back, adding each number)
sum(5) = 5 + 4 + 3 + 2 + 1 + 0 = 15
sum(10) = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 = 55
Live trace — try it yourself
Two More Simple Recursive Programs
The same pattern works for many problems. Factorial and power are two classic examples that follow the exact same structure as sum().
#include <stdio.h> /* factorial: 5! = 5 × 4 × 3 × 2 × 1 = 120 */ int factorial(int n) { if (n <= 1) return 1; /* base case — 1! = 1 and 0! = 1 */ return n * factorial(n - 1); /* recursive case */ } /* power: 2^8 = 2 × 2^7 = 2 × 2 × 2^6 ... */ int power(int base, int exp) { if (exp == 0) return 1; /* base case — anything ^ 0 = 1 */ return base * power(base, exp - 1); /* recursive case */ } int main() { printf("5! = %d\n", factorial(5)); /* 120 */ printf("2^8 = %d\n", power(2, 8)); /* 256 */ printf("10^3 = %d\n", power(10, 3)); /* 1000 */ return 0; }
5! = 120 2^8 = 256 10^3 = 1000
| Function | Base case | Recursive case |
|---|---|---|
| sum(m) | m == 0 → return 0 | return m + sum(m-1) |
| factorial(n) | n <= 1 → return 1 | return n * factorial(n-1) |
| power(b, e) | e == 0 → return 1 | return b * power(b, e-1) |
What is an Inline Function?
Every time you call a function, the CPU has to do extra work — jump to where the function lives in memory, set up a stack frame, do the work, then jump back. This is called function call overhead. For a big function it's worth it. For a tiny function that adds two numbers, the overhead can be as much work as the function itself.
An inline function solves this. You add the keyword inline before the function. The compiler sees this as a hint: "instead of making a jump to this function, just paste its code directly at the call site."
inline return_type function_name(parameters) {
body;
}
/* Example */
inline int add(int a, int b) {
return a + b;
}
What the compiler does with inline
Regular Function vs Inline Function
int add(int a, int b) { return a + b; } int main() { int x = add(3, 5); }
- CPU jumps to add() in memory
- sets up a stack frame
- does the work
- jumps back to main()
- function exists once — saves memory
inline int add(int a, int b) { return a + b; } int main() { int x = add(3, 5); }
- no jump — code pasted directly
- no stack frame setup
- faster execution
- code copied at every call site
- larger binary if called many times
| Feature | Regular | Inline |
|---|---|---|
| Call overhead | Yes — jump to function | No — code pasted directly |
| Speed | Slightly slower | Faster for tiny functions |
| Binary size | Smaller — one copy | Larger if called many times |
| Best for | Any size function | Tiny 1–3 line functions |
| Compiler obeys? | Always | It's a hint — compiler decides |
Can sum() be Inline? Inline + Recursion
You can write inline in front of sum(). It compiles fine. But here's the thing — the compiler will ignore the inline hint for recursive functions.
Why? Because inline means "paste the code at the call site". But sum(m) calls itself — to paste it, you'd need to paste infinite copies of the code inside each other. That's impossible. So the compiler quietly treats it as a regular function.
#include <stdio.h> /* inline keyword is here — but compiler ignores it for recursion */ inline int sum(int m) { if (m > 0) { return m + sum(m - 1); /* calls itself — can't be inlined */ } else { return 0; } } /* THIS can actually be inlined — no recursion, tiny, fast */ inline int square(int n) { return n * n; /* one line — perfect for inline */ } inline int isEven(int n) { return n % 2 == 0; /* one line — perfect for inline */ } int main() { printf("sum(10) = %d\n", sum(10)); /* 55 */ printf("square(7) = %d\n", square(7)); /* 49 */ printf("isEven(8) = %d\n", isEven(8)); /* 1 */ printf("isEven(9) = %d\n", isEven(9)); /* 0 */ return 0; }
sum(10) = 55 square(7) = 49 isEven(8) = 1 isEven(9) = 0
square(n), max(a,b), min(a,b), isEven(n), abs(n) — tiny one-liners called inside loops thousands of times. For everything else, regular functions are fine.Quick Quiz
What happens if a recursive function has NO base case?
What does sum(4) return based on the sum() function in this lesson?
What does the inline keyword tell the compiler to do?
Why does adding inline to the recursive sum() function have no effect?
Lesson Checklist
- A recursive function is one that calls itself
- Every recursive function must have a base case — the stopping condition
- sum(m) = m + sum(m-1) — recursive case; sum(0) = 0 — base case
- Recursion has two phases: going down (building calls) and coming back up (collecting answers)
- Without a base case: infinite recursion → stack overflow crash
- inline tells the compiler to paste function code at the call site — no jump needed
- inline is a hint — the compiler can ignore it
- inline is best for tiny 1–3 line functions like max(), square(), isEven()
- inline on recursive functions is ignored — recursion cannot be inlined
- I completed the quiz