Recursion Felt Like a While Loop — Until rBST Delete Hit Me With 4 Cases
Day 21. March 9th.
Before starting recursion, I had a quiet confidence. Not the nervous feeling I had before graphs. Not the dread before heap. A gut feeling that this one wouldn't break me.
I was mostly right.
What Is Recursion?
Recursion is when a function calls itself until it reaches a stopping condition called a base case.
Every recursive function needs two things:
Base case — when to stop
Recursive case — call itself with a smaller problem
def countdown(n):
if n == 0: # base case — stop here
return
print(n)
countdown(n - 1) # recursive case — shrink the problem by 1
Without a base case, the function calls itself forever until the stack overflows and crashes.
The Gift Box Analogy That Made It Click
Imagine a gift box. You open it and find a smaller box inside. Open that — another box. You keep going until you finally find the ball.
def open_gift_box(box):
if contains_ball(box): # base case — found the ball, stop opening
return "Found the ball!"
smaller_box = open(box) # each box contains a smaller one
return open_gift_box(smaller_box) # same process, smaller problem
open_gift_box(big_box)
└── open_gift_box(medium_box)
└── open_gift_box(small_box)
└── found ball! ✅
Two things made this analogy stick. First, the process is identical every time — you don't need different logic for each box size. Write it once, trust it to repeat. Second, the problem shrinks with every call — each box is smaller than the last, always moving closer to the answer.
That's recursion. Same process. Smaller problem. Every time.
Why Recursion Felt Like a While Loop
When I first saw a function calling itself, I wasn't shocked. Once I thought about it, recursion felt familiar — basically a while loop in disguise.
# Both do the same thing — repeat until a condition is met
# The only difference is HOW they repeat
def countdown_iterative(n):
while n > 0: # loop condition controls repetition
print(n)
n -= 1 # shrink manually
def countdown_recursive(n):
if n == 0: # base case controls repetition
return
print(n)
countdown(n - 1) # shrink by calling itself
Loop vs self-call. Same outcome. Once that clicked, recursion stopped feeling mysterious.
Call Stack — The Stack Overflow Website Finally Makes Sense
Every recursive call gets added to the call stack — Python's way of tracking which function called which. Last in, first out. Same LIFO principle from stacks earlier in my journey.
def func_three():
print("three") # runs first — top of the stack
def func_two():
func_three() # pauses func_two, pushes func_three onto stack
print("two") # runs after func_three returns
def func_one():
func_two() # pauses func_one, pushes func_two onto stack
print("one") # runs after func_two returns
func_one()
# Output: three, two, one — printing happens on the way OUT, not in
Stack builds up: Stack unwinds:
func_three() ← top func_three() → prints "three" → removed
func_two() func_two() → prints "two" → removed
func_one() ← bottom func_one() → prints "one" → removed
And stack overflow? That's when there's no base case and the stack fills up forever. The website name finally makes complete sense.
Factorial — Gift Box Meets Call Stack
def factorial(n):
if n == 1: # base case — smallest box
return 1
return n * factorial(n - 1) # need the smaller answer first, pause here
# factorial(4) → 24
Building up — opening boxes:
factorial(4) → needs factorial(3), pause
factorial(3) → needs factorial(2), pause
factorial(2) → needs factorial(1), pause
factorial(1) → base case! return 1 ✅
Unwinding — closing boxes:
factorial(1) → returns 1
factorial(2) → 2 × 1 = 2
factorial(3) → 3 × 2 = 6
factorial(4) → 4 × 6 = 24 ✅
Nothing is calculated on the way in. Everything happens on the way out.
rBST — Recursive Contains and Insert
After understanding recursion basics, applying it to BST felt natural.
# --- Recursive Contains ---
def r_contains(self, value, current=None):
if current is None: # base case 1 — fell off the tree, not found
return False
if value == current.data: # base case 2 — found the node
return True
if value < current.data:
return self.r_contains(value, current.left) # search left subtree
return self.r_contains(value, current.right) # search right subtree
# --- Recursive Insert ---
def r_insert(self, value, current=None):
if current is None: # base case — found an empty spot
return Node(value) # create the new node here
if value < current.data:
current.left = self.r_insert(value, current.left) # insert into left subtree
elif value > current.data:
current.right = self.r_insert(value, current.right) # insert into right subtree
return current # KEY: return the node back up to reconnect the tree
Same divide and conquer as iterative, just calling itself instead of looping. The key difference with insert — we return the node back up to reconnect the tree. Took a second read to fully understand why returning current matters.
rBST Delete — Where It Got Hard
Delete is where my confidence hit a wall. Four cases, each with its own logic.
Case 1 — Leaf node (no children)
50
/ \
30 70
\
40 ← delete this → return None, parent disconnects it
Case 2 — Only a right child
50
/ \
30 70 ← delete this
\
80 ← promote this up
Case 3 — Only a left child
50
/ \
30 70 ← delete this
/
60 ← promote this up
Cases 1–3 are manageable. Remove the node, hand its child (or None) to the parent.
Case 4 — Both children (the hard one)
50 50
/ \ / \
30 70 ← delete this → 30 60 ← inorder successor copied up
/ \ \
60 80 80
You can't just remove 70 — the tree splits. You need a replacement that preserves BST order. The solution: find the smallest value in the right subtree (the inorder successor), copy it into the deleted node's position, then delete that successor from below.
Why the smallest in the right subtree? It's bigger than everything on the left and smaller than everything else on the right. BST property stays intact.
Here's the full delete method with all four cases:
def r_delete(self, value, current=None):
if current is None: # value not found in the tree
return None
# --- Navigate to the target node ---
if value < current.data:
current.left = self.r_delete(value, current.left)
elif value > current.data:
current.right = self.r_delete(value, current.right)
# --- Found the node to delete ---
else:
# Case 1: leaf node — just remove it
if current.left is None and current.right is None:
return None
# Case 2: no left child — promote right child
elif current.left is None:
return current.right
# Case 3: no right child — promote left child
elif current.right is None:
return current.left
# Case 4: two children — replace with inorder successor
else:
min_val = self._min_value(current.right) # find smallest in right subtree
current.data = min_val # copy that value up
current.right = self.r_delete(min_val, current.right) # delete the duplicate below
return current # reconnect the (possibly modified) node back to its parent
Where I Am Honestly
Recursion difficulty — 6/10.
The concept was easy. The gift box analogy made it feel natural. The call stack connected back to stacks I already knew. Factorial made the unwind process clear. rBST contains and insert — straightforward.
rBST delete is where I'm still in the middle. The logic makes sense. All four cases are understandable individually. But putting it all together in one function, remembering which case does what, and trusting the recursion to handle the rest — that's where the coding confidence is still building.
Current Stats
Date: March 9, 2026 Day in journey: 21 Topics completed: Linked Lists, Stacks, Queues, BST, Hash Tables, Graphs, Heap, Recursion, rBST Daily study time: 4 hours (7 AM – 11 AM) Recursion difficulty rating: 6/10 Confidence: Logic — Coding still solidifying
Next up: Tree Traversals
Learning DSA and hitting the same walls? Drop a comment — what made recursion click for you?
— Avinash Negi
Resources:
