C Recursion

If you are new to C programming, you may have heard of the concept named recursion. You may also have heard that recursion is difficult and complex to understand and implement. Do not worry! In this article, we are going to cover the basics of recursion, recursive functions, recursive calls, and how it is different from iteration. We are also going to look into some common examples of recursion and understand how the recursion works, and its memory management among other things.

What is Recursion in C?

First, let’s start with the recursion definition,

Recursion is the process of calling a function itself repeatedly until a particular condition is met. A function that calls itself directly or indirectly is called a recursive function and such kind of function calls are called recursive calls.

In C, recursion is used to solve a complex problem. Using recursion we can solve a complex problem in a small piece of code by breaking down the problem. We can solve large numbers of problems using recursion for example factorial of a number, generating Fibonacci series, generating subsets etc.

Let’s discuss some basic terminologies and fundamentals of recursion before going into working and implementation.

Recursive Functions

A function that calls a copy of itself is called Recursive Function. The recursive functions contain a call to themselves somewhere in the function body. Moreover, such functions can contain multiple recursive calls

Basic Structure of Recursive Functions

The basic syntax structure of the recursive functions is:

type function_name (args) {
    // function statements
    // base condition
    // recursion case (recursive call)
}

Example of Recursion in C

Consider a simple problem in which we calculate the sum of the first N natural numbers and solve it using recursion.

Sum of First 5 Natural Numbers: 15

Read the above example thoroughly as we will understand the different concepts of recursion using this example.

Fundamentals of Recursion in C

The fundamental of recursion consists of two objects which are essential parts of any recursive function. These are:

1. Recursion Case
2. Base Condition

1. Recursion Case

The recursion case refers to the recursive call present in the recursive function. It decides what type of recursion will occur and the problem will be divided into smaller subproblems. 

The recursion case defined in the nSum() function of the above example is:

int res = n + nSum(n - 1);

The recursion case if often represented mathematically is a recurrence relation.

f(N) = N + f(N - 1);

This recurrence relation is used for the complexity analysis of the method.

2. Base Condition

The base condition specifies when the recursion is going to terminate. It is the condition that determines the exit point of the recursion. We have to be careful while defining the base condition because the incorrect or incomplete base condition may lead the recursion to run for infinite times.

Note: It is important to define the base condition before the recursive case otherwise, the base condition may never encountered and recursion might continue till infinity.

Considering the above example again, there is only one condition in the example which is the base condition defined for the nSum() function:

if (n == 0) {
    return 0;
}

Now that the basic terminologies and fundamentals are out of the way, let’s move on to understand how the recursion works in C.

How Recursion works?

Recursion is considered difficult to understand by many people but once you understand the working of recursion, it becomes a powerful weapon in your arsenal to battle complex problems.

To understand how C recursion works, we will again refer to the example above and trace the flow of the program. In the nSum() function, Recursive Case is

int res = n + nSum(n - 1);

In the example, n = 5, so as nSum(5)’s recursive case, we get

int res = 5 + nSum(4);

In nSum(4), the recursion case and everything else will be the same, but n = 4. Let’s evaluate the recursive case for n = 4,

int res = 4 + nSum(3);

Similarly, for nSum(3), nSum(2) and nSum(1)

int res = 3 + nSum(2);    // nSum(3)
int res = 2 + nSum(1);    // nSum(2)
int res = 1 + nSum(0);    // nSum(1)

Let’s not evaluate nSum(0) and further for now.

Now recall that the return value of the nSum() function in this same integer named res. So, instead of the function, we can put the value returned by these functions. As such, for nSum(5), we get

int res = 5 + 4 + nSum(3);

Similarly, putting return values of nSum() for every n, we get

int res = 5 + 4 + 3 + 2 + 1 + nSum(0);

In nSum() function, the base condition is

if (n == 0) {
    return 0;
}

which means that when nSum(0) will return 0. Putting this value in nSum(5)’s recursive case, we get

int res = 5 + 4 + 3 + 2 + 1 + 0;
        = 15

At this point, we can see that there are no function calls left in the recursive case. So the recursion will stop here and the final value returned by the function will be 15 which is the sum of the first 5 natural numbers.

Recursion Tree Diagram of nSum(5) Function

If you didn’t understand properly and are still confused about the recursion working, don’t worry, it is explained again in terms of memory management and the compiler’s internal handling.

Memory Allocation for Recursive Function

Now that we are done with the working of the recursion, we will look into how the recursion is internally handled by the compiler and how the memory is managed for recursive functions. Understanding this matter will further improve our insight into recursion.

All the function’s local variables and other stuff are stored inside the stack frame in stack memory and once the function returns some value, its stack frame is removed from the memory. The recursion follows a similar concept but with a little twist.

In recursion,

• A stack frame is created on top of the existing stack frames each time a recursive call is encountered and the data of each recursive copy of the function will be stored in their respective stack.
• Once, some value is returned by the function, its stack frame will be destroyed.
• The compiler maintains an instruction pointer to store the address of the point where the control should return in the function after its progressive copy returns some value. This return point is the statement just after the recursive call.
• After all the recursive copy returned some value, we come back to the base function and the finally return the control to the caller function.

It was a bit difficult to understand, wasn’t it? So let’s make use of the first example again and see how the memory is managed for the nSum() function.

Step 1: When nSum() is called from the main() function with 5 as an argument, a stack frame for nSum(5) is created.

Call Stack at Step 1

Step 2: While executing nSum(5), a recursive call is encountered as nSum(4). The compiler will now create a new stack frame on top of the nSum(5)’s stack frame and maintain an instruction pointer at the statement where nSum(4) was encountered.

Call Stack at Step 2

Step 3: The execution of nSum(4) will start, but just like the previous function, we encounter another recursive call as nSum(3). The compiler will again follow the same steps and maintain another instruction pointer and stack frame for nSum(3).

Call Stack at Step 3

Step 4: The same thing will happen with nSum(3), nSum(2), and nSum(1)’s execution.

Step 5: But when the control comes to nSum(0), the condition (n == 0) becomes true and the statement return 0 is executed.

Call Stack at Step 5

Step 6: As the value is returned by the nSum(0), the stack frame for the nSum(0) will be destroyed, and using the instruction pointer, the program control will return to the nSum(1) function and the nSum(0) call will be replaced by value 0.

Call Stack at Step 6

Step 7: Now, in nSum(1), the expression int res = 1 + 0 will be evaluated and the statement return res will be executed. The program control will move to the nSum(2) using its instruction pointer.

Call Stack at Step 7

Step 8: In nSum(2), nSum(1) call will be replaced by the value it returned, which is 1. So, after evaluating int res = 2 + 1, 3 will be returned to nSum(3). The same thing will keep happening till the control comes to the nSum(5) again.

Call Stack at Step 8

Step 9: When the control reaches the nSum(5), the expression int res = 5 + nSum(4) will look like int res = 5 + 10. Finally, this value will be returned to the main() function and the execution of nSum() function will stop.

Call Stack at Step 9

Stack Overflow

The program’s call stack has limited memory assign to it by the operating system and it is generally enough for program execution. But if we have a recursive function that goes on for infinite times, sooner or later, the memory will be exhausted and no more data can be stored. This is called stack overflow. In other words,

Stack overflow is the error that occurs occurs when the call stack of the program cannot store more data resulting in program termination.

It is one of the most common errors that is associated with the recursion.

Types of Recursion

The recursion can be classified into different types based on what kind of recursive case is present in the recursion.

1. Direct Recursion
   • Head Recursion
   • Tail Recursion
   • Tree Recursion
2. Indirect Recursion

1. Direct Recursion

Direct recursion is the most common type of recursion, where a function calls itself directly within its own body. The recursive call can occur once or multiple times within the function due to which we can further classify the direct recursion

A. Head Recursion

The head recursion is a linear recursion where the position of its one and only recursive call is at the start of the function. It is generally the first statement in the function.

B. Tail Recursion

The tail recursion is also a liner recursion like head recursion but the position of the recursive call is at the end of the function. Due to this, the tail recursion can be optimized to minimize the stack memory usage. This process is called Tail Call Optimization.

In the first example, the nSum() does the tail recursion.

C. Tree Recursion

In tree recursion, there are multiple recursive calls present in the body of the function. Due to this, while tracing the program flow, it makes a tree-like structure, hence the name Tree Recursion.

2. Indirect Recursion

Indirect recursion is an interesting form of recursion where a function calls another function, which eventually calls the first function or any other function in the chain, leading to a cycle of function calls. In other words, the functions are mutually recursive. This type of recursion involves multiple functions collaborating to solve a problem.

Examples of Recursion in C

Example 1: Program to Find the Factorial of a Natural Number using Tail Recursion.

Resursive Factorial of 5: 120 

Example 2: Program to find the Fibonacci Number using Tree Recursion

2

Example 3: Program to Illustrate the Indirect Recursion

20 10 9 4 3 1 

Applications of Recursion

Recursion is widely used to solve different kinds of problems from simple ones like printing linked lists to being extensively used in AI. Some of the common uses of recursion are:

• Tree-Graph Algorithms
• Mathematical Problems
• Divide and Conquer
• Dynamic Programming
• In Postfix to Infix Conversion
• Searching and Sorting Algorithms

Advantages of Recursion

The advantages of using recursive methods over other methods are:

1. Recursion can effectively reduce the length of the code.
2. Some problems are easily solved by using recursion like the tower of Hanoi and tree traversals.
3. Data structures like linked lists, trees, etc. are recursive in nature so recursive methods are easier to implement for these data structures.

Disadvantages of Recursion

As with almost anything in the world, recursion also comes with certain limitations some of which are:

1. Recursive functions make our program a bit slower due to function call overhead.
2. Recursion functions always take extra space in the function call stack due to separate stack frames
3. Recursion methods are difficult to understand and implement.

Conclusion

It is said that “Any problem that can be solved using iteration can also be solved with recursion and vice versa.“. So, recursion is just one of the methods to solve problems of different kinds. It provides a lot of benefits but also comes with certain limitations. It should be used when its benefits outweigh its limitations.

FAQs on Recursion in C

Q1. What is the difference between iteration and recursion?

Ans:

The following table lists the differences between recursion and iteration.

Property	Iteration	Recursion
Definition	A set of instructions repeatedly executed.	Function calls itself.
Termination	When the termination condition for the iterator ceases to be satisfied.	Through base case, where there will be no function call.
Usage	Used when code size needs to be small, and time complexity is not an issue.	Used when time complexity needs to be balanced against an expanded code size.
Time Copmlexity	Very high(generally exponential) time complexity.	Relatively lower time complexity(generally polynomial-logarithmic).
Space Complexity	The space complexity is higher than iterations.	Space complexity is lower.

To know more about the differences, refer to this article – Difference between Iteration and Recursion

Q2. What is tail call optimization?

Ans:

Tail call optimization refers to the optimizing method applicable to tail recursion in which the return value is stored by the compiler and the same stack frame is used for each recursive call instead of seperator memory.

To know more about it, refer to this article – Tail Call Elimination