Head Recursion in C

Back to: C Tutorials For Beginners and Professionals

Head (Non-Tail) Recursion in C Language with Examples

In this article, I will discuss Head (Non-Tail) Recursion in C Language with Examples. Please read our previous article discussing Tail Recursion in C Language with Examples. At the end of this article, you will understand the following pointers:

1. What is Head Recursion in C Language?
2. Multiple Real-Time Examples to Understand Head Recursion in C Language
3. Advantages of Head Recursion in C Language
4. Disadvantages of Head Recursion in C Language
5. When Would We Use Head Recursion in C language?

What is Head (Non-Tail) Recursion in C Language?

Head recursion in C language, or any programming language, is a specific form of recursion where the recursive call is the first operation performed in the function, with no other operations happening before it. This contrasts with tail recursion, where the recursive call is the last action.

In head recursion, the processing or computation occurs after the recursive call. As a result, the recursive function must wait for the return of its recursive calls before it can complete its computation. This characteristic often means that head recursive functions can’t be easily optimized like tail-recursive functions, as each recursive call needs to maintain its stack frame for the computations after the call.

Example to Understand Head Recursion in C Language:

Let us understand Head Recursion. Following is the structure of head recursion. If there is a function that is calling itself, then it is a recursive function. As you can see in the image below, the function fun calls itself, so it is a recursive function. Then, if you notice further, the first statement inside the function is the recursive call. That means that all the processing it has to do is done at a return time, i.e., after the recursive call. There is no statement that there is no operation before the function call.

Note: If something is before the recursive call, it is not a head recursion. If something is there before the function call, it is a recursion. We don’t have to give it any special name. The following is not head recursion.

What do you mean by Head Recursion in C Language?

Head Recursion means the function doesn’t have to process or perform any operation at the time of calling; it has to do everything only at the time of returning. If all the processing or operations are done at the returning time, then such recursive functions are called head recursion.

Example: Head Recursion in C Langauge

The following is an example of Head Recursion; we have already seen such examples in our previous articles. As you can see in the example below, the first statement is the recursive function call within the if block. Before the recursive call, no statement is present, which means it is not performing any operation at the calling time. Further, if you notice, after the recursive function call, the printf statement is there, which will be executed at returning time. Hence, this is an example of Head Recursion.

#include <stdio.h>
void fun(int n)
{
    if(n > 0)
    {
        fun(n-1); 
        printf ("%d", n);
    }
}

int main()
{
    fun(3);
    return 0;
}

Output: 123

Comparing Head Recursion with Loop in C Language:

Now, we will compare head recursion with loop. Before comparing, the first question is, can we convert head recursion into a loop? Yes, we can. For this, we need to write some logic. Let us see how to convert a head recursion to a loop. Please have a look at the following image.

The following code shows the complete example using a loop.

#include <stdio.h>
void fun(int n)
{
    int i = 1;
    while (i <= n)
    {
        printf ("%d", i);
        i++;
    }
}

int main()
{
  fun (3);
  return 0;
}

Output: 123

Note: The point that you need to remember is if a recursive function does some operation upon returning, then it is not easy to convert that recursive function to a loop. We need to convert by writing some logic.

Time Complexity: The time complexity of Head Recursion is O(n).

Head Recursion Examples in C Language

Head recursion is a form of recursion where the recursive call is the first operation in the function, with no other operations before it. The processing happens after the recursive call in head recursion, making it less intuitive than tail recursion. This kind of recursion is generally not as memory efficient as tail recursion because each recursive call needs to maintain its own stack frame. Let’s look at a couple of examples of head recursive programs in C, with explanations:

Example: Printing Numbers from N to 1

#include <stdio.h>

// Head recursive function to print numbers from N to 1
void printNumbers(int n) {
    if (n == 0) 
        return;
    printNumbers(n - 1);
    printf("%d ", n);
}

int main() {
    int number = 5;
    printNumbers(number);
    return 0;
}

Explanation:

• The function printNumbers takes an integer n as an argument.
• If n is 0, the function returns as the base case.
• The recursive call printNumbers(n – 1) happens before any other operation, characterizing head recursion.
• After returning from the recursive call, the function prints the current value of n.
• This results in the numbers being printed in ascending order after all recursive calls are complete.

Example: Calculating Factorial

#include <stdio.h>

// Head recursive function to calculate factorial
int factorial(int n) {
    if (n == 0) 
        return 1;
    int factPrev = factorial(n - 1);
    return n * factPrev;
}

int main() {
    int number = 5;
    printf("Factorial of %d is %d\n", number, factorial(number));
    return 0;
}

Explanation:

• The function factorial computes the factorial of an integer n.
• The base case is when n is 0, where it returns 1.
• The first operation in the function is the recursive call factorial(n – 1).
• Only after the recursive call returns the function proceeds to multiply n with the result of the recursive call (factPrev).
• The result of the multiplication is then returned.
• This process calculates the factorial of n by recursively calculating the factorial of n – 1, n – 2, …, until 1.

Key Differences Tail and Head Recursion:

• Stack Usage: Tail recursion can be optimized by the compiler to use constant stack space, while head recursion uses stack space proportional to the depth of the recursion.
• Performance: Because of the potential for compiler optimization, tail recursion can be more efficient than head recursion.
• Conversion: Sometimes, head recursion can be converted into tail recursion using accumulators or changing the approach to make the recursive call the last operation.

Advantages and Disadvantages of Head Recursion in C Language

Head recursion in programming, including in the C language, has advantages and disadvantages. Understanding these can help in deciding when and how to use head recursion effectively.

Advantages of Head Recursion in C Language

• Natural Problem Expression: Some problems are more naturally expressed in a head recursive manner. It can be intuitive for tasks like parsing or walking through hierarchical structures (like trees or linked lists) where you need to perform actions after recursive calls.
• Maintains State Before Recursion: In head recursion, the current state of the function is maintained before making the recursive call. This can be useful in scenarios where you must process or use the current state after exploring deeper levels (e.g., backtracking algorithms).
• Readability: For problems that are inherently recursive, a head recursive solution can be more readable and easier to understand compared to iterative solutions or even tail recursion in some cases.

Disadvantages of Head Recursion in C Language

• Stack Overflow Risk: Head recursion can lead to a stack overflow if the recursion depth is very large. This is because each recursive call consumes stack space for its local variables and returns the address until the base case is reached.
• Performance Overhead: Each recursive call involves overhead, such as saving the current function’s state and setting up the new call’s state. This can be inefficient, especially if the recursion depth is large.
• No Tail Call Optimization: Unlike tail recursion, head recursive functions cannot benefit from tail call optimization (TCO) in compilers. This means that the compiler cannot optimize away the additional stack frames, leading to potential inefficiency in terms of memory usage.
• Difficulty in Understanding and Debugging: For some programmers, especially those new to recursion, head recursive solutions can be less intuitive and harder to debug than iterative solutions.
• Limited to Specific Problems: Head recursion is not always the most efficient or straightforward approach for all types of problems. It is best suited to problems that naturally fit a recursive pattern, where processing after each recursive call is essential.

When should we use head recursion in C language?

The use of head recursion depends on the specific characteristics of the problem you’re solving. Here are some key considerations:

• Natural Problem Decomposition: Use head recursion when a problem naturally decomposes into a subproblem, followed by a post-processing step. In such cases, the solution to the problem is built up after returning from the recursive call.
• Building Solutions in Reverse: Head recursion can be useful when you need to build the solution in a reverse manner. For example, head recursion can be a natural fit in problems where the final solution depends on the outcomes of the recursive calls.
• Tree Traversal: In tree data structures, head recursion is often used for traversals where processing the root node after recursive calls to the children is required, such as in post-order traversal.
• Simple Understanding and Implementation: In some cases, head recursion can be simpler and more intuitive to implement, especially when the problem’s nature is inherently recursive.
• Maintaining State: Head recursion can be useful when the state needs to be maintained or modified before making the recursive call. This is because any state changes are naturally undone as each recursive call returns, which can simplify certain algorithms.

In the next article, I will discuss Direct Recursion in C Language with Examples. In this article, I try to explain Head Recursion in C Language with Examples. I hope you enjoy this Head Recursion in C Language with Examples article.