# 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.

```text
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:

```text
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:

```text
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:

```c
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:

```text
countdown(3)
```

The calls happen like this:

```text
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:

```text
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:

```text
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:

```text
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.