Python Recursion – GATE CSE Questions with Stack Trace
Recursion is favorite topic of GATE CSE. Every year output question is asked. Let’s master it.
What is Recursion?
When a function calls itself, it is called recursion. It needs 2 things:
- 1. Base Case: Condition to stop recursion
- 2. Recursive Case: Function calling itself
def fact(n):
if n == 0: # Base Case
return 1
else:
return n * fact(n-1) # Recursive Case
print(fact(5)) # Output: 120
Stack Trace – How Recursion Works in Memory
GATE always asks about stack memory in recursion.
fact(3)
-> fact(3) calls fact(2)
-> fact(2) calls fact(1)
-> fact(1) calls fact(0)
-> fact(0) returns 1
-> fact(1) returns 1*1 = 1
-> fact(2) returns 2*1 = 2
-> fact(3) returns 3*2 = 6
Each call is stored in System Stack (LIFO).
GATE PYQ on Recursion
Q1. GATE CSE 2020 – Output Question
def fun(n):
if n == 0:
return 0
return n + fun(n-1)
print(fun(3))
Ans: 3+2+1+0 = 6
Q2. GATE CSE 2018 – Recursion + Stack
def foo(n):
if n>0:
foo(n-1)
print(n)
foo(n-1)
foo(2)
Ans: 1 2 1 . This is tricky binary recursion.
Q3. Time Complexity of Recursion
Q: T(n) = 2T(n/2) + n, What is complexity?
Ans: O(n log n) using Master Theorem. Very important for GATE.
Recursion vs Iteration – GATE Point
| Feature | Recursion | Iteration |
|---|---|---|
| Memory | More (Stack) | Less |
| Speed | Slower | Faster |
| Code | Short | Long |
Conclusion
For GATE: Recursion uses Stack, needs Base Case, otherwise Stack Overflow. Practice 20 recursion output questions.
Next Post: Time Complexity of Python Loops GATE.