Lesson 4 of 8 · Functions and Arrays · 3 min read · Updated
Recursion
A function that calls itself on a smaller problem — the base case that stops it, and the stack that holds each call.
A recursive function solves a problem by calling itself on a smaller version of it. Every recursive function needs two parts: a base case that answers directly, and a recursive case that moves closer to it.
#include <stdio.h>
int factorial(int n)
{
if (n <= 1) {
return 1; /* base case */
}
return n * factorial(n - 1); /* recursive case */
}
int sum_digits(int n)
{
if (n == 0) {
return 0;
}
return n % 10 + sum_digits(n / 10);
}
int main(void)
{
printf("5! = %d\n", factorial(5));
printf("sum of digits of 4127 = %d\n", sum_digits(4127));
return 0;
}
5! = 120
sum of digits of 4127 = 14
The Fibonacci series
#include <stdio.h>
int fib(int n)
{
if (n < 2) {
return n; /* fib(0) = 0, fib(1) = 1 */
}
return fib(n - 1) + fib(n - 2);
}
int main(void)
{
for (int i = 0; i < 10; i++) {
printf("%d ", fib(i));
}
printf("\n");
return 0;
}
0 1 1 2 3 5 8 13 21 34
Warning
Without a base case — or with one it never reaches, such as calling factorial(-1) with the test n == 1 — the calls never stop, the stack fills up and the program crashes with a stack overflow. Always check the base case first.
Note
Recursion is not faster than a loop — fib(40) this way makes hundreds of millions of calls. Use it when the problem is naturally self-similar: tree structures, folders inside folders, divide-and-conquer sorting. For a simple count, a loop is better.
What must every recursive function have so it can stop?
Try this now
- Write a recursive
power(base, exp): power(2, 10) should give 1024. - Write a recursive function that prints the digits of a number in reverse: 4127 → 7214.
- Write a recursive function that counts down from n to 1 and then prints "Go!".
Create a free account to save your progress, or sign in.