In the previous lessons, we explored:

• What recursion is

• How to write recursive functions in C

• How recursion works using the call stack

• How recursion can process strings and arrays

So far, many of our examples focused on performing actions, such as printing values.

But recursion becomes much more powerful when functions return values.

In this lesson, we will learn how recursive functions build results step by step and return them back through the call stack.

1. Returning Values From Functions

You already know that functions can return values.

Example:

int square(int x)
{
    return x * x;
}

If we call:

square(4)

The function returns:

16

Simple enough.

But recursion is slightly different.

In recursion, each function call waits for another call to return a value first.

2. How Recursive Returns Work

In a recursive function:

1. The function calls itself

2. That call calls another one

3. Eventually the base case returns a value

4. Then the results move back up the call stack

This is called building the result during stack unwinding.

3. Conceptual Example: Summing Numbers

Imagine a function that adds numbers down to zero.

Conceptually:

sum(4)
= 4 + sum(3)

sum(3)
= 3 + sum(2)

sum(2)
= 2 + sum(1)

sum(1)
= 1 + sum(0)

sum(0)
= 0

Now the recursion stops.

Then the results are returned step by step.

4. How the Result Is Built

When the base case returns, the stack unwinds.

sum(0) returns 0

sum(1) returns 1 + 0 = 1

sum(2) returns 2 + 1 = 3

sum(3) returns 3 + 3 = 6

sum(4) returns 4 + 6 = 10

The final answer becomes 10.

Notice something important:

Each function waits for the next recursive call before finishing its calculation.

5. A Simple C Example

Here is how this concept looks in C.

int sum(int n)
{
    if (n == 0)
        return 0;

    return n + sum(n - 1);
}

Let’s examine the parts.

Base Case

if (n == 0)
    return 0;

This stops recursion.

Recursive Case

return n + sum(n - 1);

The function adds n to the result of the smaller problem.

6. Understanding the Execution

If we call:

sum(4)

The calls look like this:

sum(4)
sum(3)
sum(2)
sum(1)
sum(0)

Then the results return upward through the stack.

0
1
3
6
10

Each call contributes part of the final result.

7. Another Way to Think About It

When recursion returns values, each function does two jobs:

1. Break the problem into a smaller piece

2. Combine its own contribution with the returned result

This pattern appears in many recursive algorithms.

---

8. A Conceptual Example With Strings

Imagine a function that processes characters in a string.

Conceptually it might:

1. Handle the first character

2. Recursively process the rest of the string

3. Combine the results

The idea remains the same.

Each step:

• reduces the problem

• waits for the recursive call

• builds part of the final answer

---

9. A Common Beginner Mistake

Many beginners forget that the recursive call must return something useful.

Example mistake:

sum(n)
{
    sum(n-1);
}

This function calls itself but never builds a result.

When writing recursive functions that return values, always ask:

• What does the recursive call return?

• How does the current function use that result?

---

10. How to Design Recursive Functions That Return Values

A good strategy is to think in three steps.

Step 1: Identify the Base Case

What is the smallest version of the problem?

Example:

n == 0

---

Step 2: Solve a Smaller Version

Call the function with a smaller input.

Example:

sum(n - 1)

---

Step 3: Combine the Result

Use the returned value to build the final result.

Example:

n + sum(n - 1)

---

Key Ideas From This Lesson

Recursive functions that return values work by:

• Breaking problems into smaller subproblems

• Solving the smallest case first

• Building the result while the stack unwinds

Every recursive call contributes a piece to the final answer.

---

What Comes Next

You now understand the core building blocks of recursion:

• base cases

• recursive calls

• call stacks

• returning values

In the next lesson, we will explore how to design recursive solutions systematically.

You will learn how to recognize problems that naturally fit recursion and how to break them into smaller steps before writing any code.