Recursion Basics

Part of the Fundamentals section of Coddy's C journey — lesson 50 of 63.

Recursion is a technique where a function calls itself to solve a problem. It's like solving a big problem by breaking it into smaller, similar problems.

Let's look at a simple recursive function that calculates factorial:

int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n <= 1) {
        return 1;
    }
    
    // Recursive case: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Every recursive function needs:

A base case to stop recursion
A recursive case that moves toward the base case

For example, calculating factorial(3):

factorial(3) calls factorial(2)
factorial(2) calls factorial(1)
factorial(1) returns 1 (base case)

factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6

Challenge

Easy

Create a function named sumToN that uses recursion to calculate the sum of numbers from 1 to n.

For example:

sumToN(3) should return 6 (1 + 2 + 3)
sumToN(5) should return 15 (1 + 2 + 3 + 4 + 5)

Your function should:

Use a base case when n is 1 (return 1)
Otherwise, return n plus the sum of numbers from 1 to (n-1)

Cheat sheet

Recursion is a technique where a function calls itself to solve a problem by breaking it into smaller, similar problems.

Every recursive function needs:

A base case to stop recursion
A recursive case that moves toward the base case

Example - factorial function:

int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n <= 1) {
        return 1;
    }
    
    // Recursive case: n! = n * (n-1)!
    return n * factorial(n - 1);
}

How factorial(3) executes:

factorial(3) calls factorial(2)
factorial(2) calls factorial(1)
factorial(1) returns 1 (base case)
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6

Try it yourself

#include <stdio.h>

// Write your sumToN function here

// Don't change the main() function
int main() {
    int n;
    scanf("%d", &n);
    
    printf("%d", sumToN(n));
    return 0;
}

Test yourself

This lesson includes a short quiz. Start the lesson to answer it and track your progress.

All lessons in Fundamentals

1Introduction

C Language Hello World!Comments Basic Program Structure

4Control Flow

If Statement If - Else Else-If Switch Case Ternary Conditional Operator Recap Challenge Nested If - Else

7Functions

Declare a Function Return Types Parameters Recap Challenge #1Recursion BasicsFunction Prototypes Recap Challenge #2