How Recursion Uses Stack in C

Back to: C Tutorials For Beginners and Professionals

How Recursion Uses Stack in C Language with Examples

In this article, I am going to discuss How Recursion uses Stack in C Language with Examples. Please read our previous article discussing the basic concept of Recursive Functions in C Language with Examples.

How Recursion Uses Stack in C Language?

Recursion in C programming involves a function calling itself to solve a smaller part of the problem until a base condition is met. This process uses the system stack in several key ways:

Function Calls and the Stack: Each time a recursive function is called, a new instance of that function is placed on the stack. This instance contains the function’s local variables and the return address.

Working with the Stack Frame:

• Creating a Stack Frame: A stack frame is created when a function is called. This frame stores the function’s local variables and the return address.
• Stack Frame for Each Recursive Call: Each recursive call creates its own stack frame on top of the previous one. This is essential for the function to remember its state and variables for each call.

Base Case and Unwinding:

• Base Case: This is a condition in the recursive function that does not make a recursive call. Reaching the base case is crucial to stop the recursion.
• Unwinding the Stack: Once the base case is reached, the function starts returning, and its stack frames are popped off the stack. This unwinding continues until the original call is reached and the stack is empty.

Memory Considerations:

• Stack Overflow: If the recursive calls are too deep or the base case is not properly defined, it can lead to a stack overflow, where the stack space allocated for the program is exhausted.
• Optimization: Tail recursion, where the recursive call is the last operation in the function, can be optimized by compilers to reuse stack frames, thus saving memory.

Example to Understand How Recursion Uses Stack in C Language?

We already discussed that the memory is used by dividing it into three sections i.e. code section, stack section, and heap section. We will take the following example and show you how the stack is created and utilized as a recursive function.

As shown in the above example, we have two functions: fun1() and the main() function. The machine code of these two functions will be there in the code section of the main memory. Let us run the program and see how the stack is created.

The program execution starts from the main functions. Inside the main function, int x=3 is the first statement that is the x variable created. Inside the stack, the activation record for the main function is created, and it will have its own variable, that is, x having value 3.

The next statement is fun1(), i.e., call to the fun1 function. So, once the function fun1() is called, it has just one variable: n. The activation record for that fun1() function is created, and it will have that variable n, and the value x is passed to that n variable, so it will store the value 3. For a better understanding, please have a look at the below image. This is the first call of the fun1 function.

Let’s continue. Inside the fun1 function, first, it will check whether n is greater than 0. Yes, n (3) is greater than 0, and the condition satisfies. So, it will print the value 3 and call the fun1() function with the reduced value of n, i.e., n-1, i.e., 2. Once the fun1 function is called, again another activation record for that function is created inside the stack. The variable n is again created within this activation record with the value 2, as shown in the image below. This is the second call of the fun1 function.

In the second call, first, it will check whether n is greater than 0. Yes, n (i.e., 2) is greater than 0, and the condition satisfies. So, it will print the value 2 and call the fun1() function with the reduced value of n, i.e., 2-1, i.e., 1. Once the fun1 function is called, another activation record for that function is created, and the variable n is created with the value 1, as shown in the below image. This is the third call of the fun1 function.

The third fun1 function call will check whether n is greater than 0. Yes, n (i.e., 1) is greater than 0. So, it will print the value 1, and again, it will call the fun1() function with the reduced value of n, i.e., 1-1, i.e., 0. Once the fun1 function is called, another activation record for the fun1 function is created, and the variable n is created with the value 0, as shown in the below image. This is the fourth call of the fun1 function.

Now, the fourth fun1 function call will check whether n is greater than 0. No, n (i.e., 0) is not greater than 0. So, it will not come inside the condition and will not execute those two statements; it simply comes out of the function. Once the fourth fun1 function call is completed, it will delete that fourth fun1 activation area from the stack, as shown in the image below.

Once that function call is completed and once that activation record is deleted from the stack, the control goes back to the previous function call i.e. fun1(1) i.e. the third function call. In the third fun1 function call, there are no more operations to perform, so it simply comes out from that function to the previous function call and deletes the activation record from the stack, as shown in the below image, created for the third function call.

Once that activation record is deleted from the stack, the control returns to the previous function call, i.e., fun1(2), i.e., the second function call. In the second fun1 function call, there are no more operations to perform, so it simply comes out from that function to the previous function call and deletes the activation record from the stack created for the second function call, as shown in the image below.

Once that activation record for the second function call is deleted from the stack, the control returns to the previous function call, i.e., fun1(3), i.e., the first function call. In the first fun1 function call, there are no more operations to perform, so it simply comes out from that function to the main function and deletes the activation record from the stack created for the first function call, as shown in the image below.

Nothing is inside the main function after the fun1 function call, so it will also delete the activation record created for the main function, as shown in the image below.

This is how a stack is created and utilized in a recursion.

What is the size of the stack?

Leaving the main function activation record, there are four activation records created for the fun1 function. So, the size of the stack is 4. Each activation record has just one variable, n, and we have four activation records. So, the total size is 4 * the size of the variable n.

Note: For x = 3, we have four calls. If x = 4, then we have five calls. So, for n, there will be n+1 calls and an n+1 activation record.

From this, we understand that recursive functions utilize the stack. Here, internally, it takes some extra memory for the stack. Hence, recursion is a memory-consuming function.

In the next article, I will discuss How to find the time complexity of recursive functions in the C Language. In this article, I try to explain how recursion uses stack in C language with examples, and I hope you enjoy this article. Please give your feedback and suggestions about this article, How Recursion Uses Stack in C Programming Language.