Recursion in C

Recursion is a programming concept where a function calls itself to solve a problem by breaking it down into smaller, simpler versions of the same problem. It involves defining a base case to stop the recursive calls and a recursive step that reduces the problem size until the base case is reached. This approach allows elegant and concise solutions for certain problems, like traversing tree structures or calculating factorials. However, it requires careful handling to prevent infinite loops and efficient use of system resources.

Base case: Recursion involves a base case that stops the recursive calls to prevent infinite loops, ensuring program termination.

Recursive call The recursive call is the code executed repeatedly inside the recursive function while making recursive calls.

Recursive Function

Syntax

The function call inside the main function is normal call, it calls the recursive_fun() function inside which there is another function call recursive_fun(); which is termed as recursive call and the whole recursive_fun() function is recursive function. Base_case is the stopping condition for the recursive function.

How does Recursion in C work?

The recursion is possible using a method or function in C language. The recursive function or method has two main parts in its body, i.e., the base case and the recursive case. While the recursive method is executed, first, the base case is checked by the program. If it turns out true, the function returns and quits; otherwise, the recursive case is executed. Inside the recursive case, we have a recursive call that calls the function inside which it is present.

The representation of recursion in the program is as follows.

In the following image, there is a recursive function inside which there is a recursive call that calls the recursive function until the condition of the problem is true. If the condition gets satisfied, then the condition is false, and the program control goes for the remaining statements and stops the program.

Types of Recursion in C

There are two types of recursion in the C language.

1. Direct Recursion
2. Indirect Recursion

1. Direct Recursion

Direct recursion in C occurs when a function calls itself directly from inside. Such functions are also called direct recursive functions.

Following is the structure of direct recursion.

In the direct recursion structure, the function_01() executes, and from inside, it calls itself recursively.

2. Indirect Recursion

Indirect recursion in C occurs when a function calls another function and if this function calls the first function again. Such functions are also called indirect recursive functions.

Following is the structure of indirect recursion.

In the indirect recursion structure the function_01() executes and calls function_02(). After calling now, function_02 executes where inside it there is a call for function_01, which is the first calling function.

C Program Function to show direct recursion

Here is a simple C program to print the Fibonacci series using direct recursion.

Code:

Output:

Learn more about Fibonacci Series Program in C Using Recursion.

C Program Function to show indirect recursion

Here is a C program to print numbers from 1 to 10 in such a manner that when an odd no is encountered, we will print that number plus 1. When an even number is encountered, we would print that number minus 1 and will increment the current number at every step.

Code:

Output:

In this C program we have function named odd() and even(). A variable n is assigned with a value 1 as we have to take values from 1 to 10. Now inside the odd() function, we have an if statement which states that if the value of n is less than or equals 10 add 1 to it and print. Then the value of n is incremented by 1(it becomes even), and the even() function is called. Now inside the even() function, we again have an if statement which states that if the value of n is less than or equals 10 subtract 1 from it and print. Then the value of n is incremented by 1(it becomes odd, and the odd() function is called. This indirect recursion goes on until the if condition inside both the functions becomes unsatisfied. At last, we have the main() function inside, which we call the odd() function as the first number handle is 1, which is odd.

Now let's simulate this program using stack and the concept called activation record by which we could track program logic in respect of program stack.

In the following images:

• Act means "Activation Record"
• o means odd()
• e means even()
• m means main()

Here, the activation record is denoted by Act, odd() is represented by o, even() by e, and main() is represented by m. Upon executing the program at first, the main() function is executed, which causes the activation record Act m to be stored in the stack. The main function calls the odd() function, so the activation record Act o is next added to the stack. Now inside odd() there is a call for even() so the activation record Act e is added in the stack and this process goes on until the base conditions inside the odd() and even() function are reached. Now that the base conditions are met, the activation records are removed from the stack, and the value inside that activation record is returned, but in the above example, functions are void. They don't return any value.

Let's take a few more examples of recursion to understand it in a better way.

Examples of Recursion in C

C Program to show infinite recursive function

Code:

In this program, there is a call for main() function from inside main() function. But we have not given exit conditions for the program. Therefore, the program will print 'Scaler' infinite times as output.

Hence, this happens when you run a program without a base case.

C program to calculate factorial of a number using recursion

Code:

Output:

In the above C program, we are calculating the factorial using recursion. Here we declare variable n inside which the number is stored whose factorial is to be found. The function factorial_01 calculates the factorial of that number. In the factorial_01 function, if the value of n=0, then it returns 1, which is the base condition of the function. Else factorial(n-1) is recursively computed first and then multiplied to n. The factorial value is stored inside the fact that we print in the end.

Sum of Natural Numbers Using Recursion

Code:

Output:

Explanation: In the above program, the sum() function is invoked from the main() function in which the integer value is passed as an argument. In sum() function, we pass an integer variable 'a' and if it is non-zero, then it returns an expression with a recursive call to the sum(a-1) function, and it continues until the value of a is equal to 0. When a is zero, the condition if sum() fails and returns the value of 'a'.

For example, if we start with sum(3). As a=3 is not equal to 0 then the sum(3) function will return 3+sum(2) by calling sum(2) recursively, as a=2 not equal to 0 sum(2) will return 2+sum(1) by calling sum(1) recursively, as a=1 not equal to 0 sum(1) will return 1+sum(0) and as a==0 became true sum(0) will return 0. As sum(1)=1+sum(0) it will became 1, sum(2)=2+sum(1) it will became 3, sum(3)=3+sum(2) it will became 6. As a result sum(3) return 6 as a result of sum of first 3 natural numbers.

Memory Allocation Of Recursive Method

Since recursion is a repetition of a particular process and has so much complexity, the stack is maintained in memory to store the occurrence of each recursive call. Each recursive call creates an activation record(copy of that method) in the stack inside the memory when recursion occurs. Once something is returned or a base case is reached, that activation record is de-allocated from the stack, and that stack gets destroyed.

Each recursive call whose copy is stored in a stack stored a different copy of local variables declared inside that recursive function.

Let's consider a C program to demonstrate the memory allocation of the recursive method.

Code:

Output:

Explanation: In this C program rfunc() is a recursive function. When entering a digit, the function subtracts 1 with each recursive call from that digit and prints it until it encounters 0, and if it encounters 0, it terminates the function immediately.

Memory Allocation:

The first call to the function rfunc() having value a=5 will lie as a copy on the bottom of the stack, and it is also the copy that will return at the end. Meanwhile, the rfunc() will call another occurrence of the same function but with 1 subtracted, i.e., a=4. Each time a new occurrence is called, it is stored at the top of the stack, which goes on until the condition is satisfied. As the condition is unsatisfied, i.e., a=0, there will be no further calls, and each function copy stored in the stack will start to return its respected values, and the function will now terminate. Therefore, in this way, the memory allocation of recursive function occurs.

Why Stack Overflow occurs in recursion?

When the base case is not reached due to an incorrect definition or if the base case is not defined, it may lead to a stack overflow error as the stack space or memory will be filled with recursion calls. For example:

So in this, if we pass the function with a value less than 1000, we will never reach any base condition so it will lead to a stack overflow error.

Advantages & disadvantages of using recursion

Advantages:

1. The code becomes shorter and reduces the unnecessary calling to functions.
2. Useful for solving formula-based problems and complex algorithms.
3. Useful in Graph and Tree traversal as they are inherently recursive.
4. Recursion helps to divide the problem into sub-problems and then solve them, essentially divide and conquer.

Disadvantages:

1. The code becomes hard to understand and analyze.
2. A lot of memory is used to hold the copies of recursive functions in the memory.
3. Time and Space complexity is increased.
4. Recursion is generally slower than iteration.