Scribd
Upload
6 views3 pages

Understanding Recursion in Stack

The document explains the execution of a recursive Java function, simpleRec, which prints numbers in a specific order based on recursive calls. It details the step-by-step execution, illustrating how the call stack operates and how the function unwinds after reaching the base case. The final output of the function is a mirrored sequence of numbers printed in a depth-first traversal manner.

Uploaded by

aishanikhan632
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views3 pages

Understanding Recursion in Stack

The document explains the execution of a recursive Java function, simpleRec, which prints numbers in a specific order based on recursive calls. It details the step-by-step execution, illustrating how the call stack operates and how the function unwinds after reaching the base case. The final output of the function is a mirrored sequence of numbers printed in a depth-first traversal manner.

Uploaded by

aishanikhan632
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Let's break it down step by step to understand how recursion unfolds in a stack using simpleRec(3).

### Code:
```java
public void simpleRec(int n) {
if (n == 0)
return;

simpleRec(n - 1); // First recursive call


[Link](n); // Output statement
simpleRec(n - 1); // Second recursive call
}
```

### Tracing the Execution for simpleRec(3)


#### Step 1: Initial Call (n = 3)
- Calls simpleRec(2)
- Waits for simpleRec(2) to finish before printing 3
- Calls simpleRec(2) again after printing

### Step-by-Step Execution (Stack Behavior)


The function follows this pattern:
1. Recursively call itself with n - 1 (first recursion).
2. Print n when the first recursion returns.
3. Recursively call itself with n - 1 again (second recursion).

This forms a recursive tree, as shown below:

simpleRec(3)
|
---------------------------------
| |
simpleRec(2) simpleRec(2)
| |
----------- -----------
| | | |
simpleRec(1) simpleRec(1) simpleRec(1) simpleRec(1)
| | | |
----------- -----------
| | | |
simpleRec(0) simpleRec(0) simpleRec(0) simpleRec(0)

### Detailed Execution Flow (Using Stack)


#### Function Calls & Prints:
1. simpleRec(3) calls simpleRec(2).
2. simpleRec(2) calls simpleRec(1).
3. simpleRec(1) calls simpleRec(0), which returns immediately.
4. Print 1.
5. simpleRec(1) calls simpleRec(0), which returns immediately.
6. Return to simpleRec(2).
7. Print 2.
8. simpleRec(2) calls simpleRec(1).
9. simpleRec(1) calls simpleRec(0), which returns immediately.
10. Print 1.
11. simpleRec(1) calls simpleRec(0), which returns immediately.
12. Return to simpleRec(3).
13. Print 3.
14. simpleRec(3) calls simpleRec(2).
15. (This is identical to steps 2-12, repeating for the second simpleRec(2)).

### Final Output (Print Order)


1
2
1
3
1
2
1

### Understanding How the Stack Works


Each recursive function call is pushed onto the call stack, and execution pauses until that function
returns.
The function follows a depth-first traversal, similar to a binary tree traversal.

| Call Stack at Peak Depth (n=3) |


|--------------------------------|
| simpleRec(0) (returns) |
| simpleRec(1) (prints 1) |
| simpleRec(0) (returns) |
| simpleRec(2) (prints 2) |
| simpleRec(0) (returns) |
| simpleRec(1) (prints 1) |
| simpleRec(0) (returns) |
| simpleRec(3) (prints 3) |

Each return statement causes the program to backtrack, printing numbers in a mirrored sequence.

### Key Takeaways


1. First recursive call (left side) is completed first.
2. Printing happens in the middle (in-order traversal).
3. Second recursive call (right side) mirrors the first one.
4. Each function call gets pushed onto the stack until it reaches n = 0, then it unwinds.

This structure is perfect for stack recursion practice because it helps visualize how function calls are
pushed and popped.

You might also like