Writing Recursive Functions in C

In the previous lesson, we introduced the idea of recursion.

We learned that recursion happens when:

A function calls itself to solve a smaller version of the same problem.

But understanding the concept is only the first step.

Now we need to learn how recursive functions are actually written in C.

In this lesson we will focus on:

• The structure of recursive functions

• The importance of the base case

• How recursive calls move toward the solution

• How recursion executes inside the program

We will focus on understanding the pattern, not memorizing specific solutions.

1. The Structure of a Recursive Function

Almost every recursive function follows the same pattern.

if (base case)
    return result
else
    return function(smaller problem)

This means every recursive function must answer two questions:

1. When should the recursion stop?

2. How does the problem become smaller each time?

If you cannot clearly answer both questions, recursion will not work.

2. Understanding the Base Case

The base case is the stopping condition.

It is the simplest version of the problem that can be solved directly.

For example, imagine a function that repeatedly reduces a number until it reaches zero.

The base case would be:

when number == 0

Once that condition is reached, the function stops calling itself.

Without a base case, the function would call itself forever.

This would eventually cause the program to crash.

3. Understanding the Recursive Case

The recursive case is where the function calls itself.

But it must call itself with a smaller version of the problem.

For example:

solve(n) calls solve(n - 1)

Each step moves the problem closer to the base case.

Eventually the smallest case is reached and recursion stops.

4. A Simple Example of Recursion

Let’s imagine a function that counts down from a number to zero.

The idea would be:

1. Print the number

2. Call the function again with a smaller number

3. Stop when the number reaches zero

A recursive version could look like this:

void countdown(int n)
{
    if (n == 0)
    {
        printf("Done\n");
        return;
    }

    printf("%d\n", n);
    countdown(n - 1);
}

Notice the structure:

• The base case stops the recursion

• The recursive case reduces the number

Each call moves closer to the stopping condition.

5. Tracing Recursive Execution

Understanding recursion requires tracing how functions execute.

Let’s imagine we call:

countdown(3)

The calls happen like this:

countdown(3)
countdown(2)
countdown(1)
countdown(0)

Once the base case is reached, the function stops calling itself.

This chain of calls is managed by something called the call stack.

6. The Call Stack

Every time a function runs, it is placed on the call stack.

When a function calls another function:

• The new function is placed on top of the stack

• The previous function waits

For recursion, the same function is placed on the stack multiple times.

Example stack progression:

countdown(3)
countdown(2)
countdown(1)
countdown(0)

Once the base case returns, the functions start finishing one by one.

Understanding this stack behavior is key to understanding recursion.

7. A Second Example to Think About

Imagine a function that repeatedly halves a number until it reaches 1.

Conceptually the steps would be:

halve(16)
halve(8)
halve(4)
halve(2)
halve(1)

Again we see the same pattern:

• A base case (number == 1)

• A recursive call with a smaller value

This structure appears in many recursive algorithms.

8. Common Mistakes When Writing Recursion

Students often struggle with recursion because of a few common mistakes.

Missing Base Case

If you forget the base case, the function never stops calling itself.

This leads to infinite recursion.

Recursive Step Does Not Reduce the Problem

If the recursive call does not make the problem smaller, the base case will never be reached.

Example mistake:

function(n)
{
    return function(n);
}

This will run forever.

Base Case That Is Never Reached

Sometimes the base case exists but the logic never reaches it.

Always verify that each recursive call moves closer to the stopping condition.

9. How to Approach Recursive Problems

When writing a recursive function, start with these steps.

Step 1: Identify the Smallest Case

What is the simplest version of the problem?

That becomes the base case.

Step 2: Break the Problem Into a Smaller Version

How can the function reduce the problem slightly?

That becomes the recursive call.

Step 3: Make Sure the Problem Shrinks

Every recursive call must move closer to the base case.

10. Practice Thinking Recursively

Before writing full solutions, try reasoning through these problems conceptually.

For example:

1. If you wanted to repeatedly remove the first character of a word until nothing remains, what would the base case be?

2. If a function repeatedly subtracts 2 from a number until it becomes zero or negative, how would the recursive step work?

3. If a number is repeatedly divided by 3 until it becomes 1, what condition should stop the recursion?

Focus on identifying:

• the base case

• the smaller problem

That thinking process is more important than the exact code.

Key Ideas to Remember

Recursive functions always contain:

• A base case that stops the recursion

• A recursive case that calls the function again with a smaller problem

And every recursive call must move closer to the base case.

What’s Next

In the next lesson, we will apply recursion to strings and arrays.

You will see how recursion can be used to process data step by step, such as examining one character of a string at a time.

Those examples will help you build the thinking needed for the upcoming project tasks.