Mental Checklist
# RECURSION - MENTAL CHECKLIST
# ----------------------------
# Recursion is hard for almost everyone at first.
# It requires a different way of thinking than loops.
# When you see a recursion problem, always answer these questions:
#
# MEMORIZE THIS:
# --------------------------------------
# 1) What is the smallest posible input?
# -> Base case
#
# 2) What should happen at that smallest input?
# -> Return value
#
# 3) How does the problem get smaller?
# -> Recursive step
#
# 4) What stays the same?
# -> Structure
#
# 5) What does the function return?
# -> Never forget this
#
# KEY IDEA:
# ----------------------------------------
# Recursion is just stacked function calls.
# Nothing magical.
#
# countdown(3)
# print(3)
# countdown(2)
# print(2)
# countdown(2)
# print(1)
# countdown(1)
# return
#
# TRACE ON PAPER
# -------------------------------
# Always trace recursion on paper.
#
# countdown(3)
# countdown(2)
# countdown(1)
# countdown(0)
# --------------------------------
def countdown(n):
if n == 0: # Base case
return
print(n)
countdown(n-1) # Smaller problem
countdown(3)
# ----------
# 3
# 2
# 1
Return Value
# RECURSION that RETURNS a value
# ------------------------------
# Problem:
# Sum all numbers from 1 to n
# Result:
# sum_to(4) = 1 + 2 + 3 + 4 = 10
#
# THE 5-STEP MENTAL CHECKLIST (APPLIED)
# -------------------------------------
# 1) What is the smallest posible input?
# - n = 1
#
# 2) What should happen at that smallest input?
# - return 1
# - the sum of numbers up to 1 is 1
#
# 3) How does the problem get smaller?
# - Insteed of summing up to n, sum up to (n - 1)
#
# 4) What stays the same?
# - The idea: "sum numbers from 1 to n"
# - The function logic does NOT change
#
# 5) What does the function return?
# - A number (the sum)
# - Every recursive call MUST return a number
#
# TRACE THE EXECUTION (DO NOT SKIP)
# ---------------------------------
# Write this on paper:
#
# sum_to(4)
# = 4 + sum(3)
# = 4 + (3 + sum(2))
# = 4 + (3 + (2 + sum(1)))
# = 4 + (3 + (2 + 1))
# = 10
# --------------------------------
def sum_to(n):
if n == 1: # Base case
return 1
print(n) # 4, 3, 2
return n + sum_to(n-1) # Smaller problem
result = sum_to(4)
print(result)
# ---------------
# 4
# 3
# 2
# 10
BST Insert
# BINARY SEARCH TREE (BST) - RECURSIVE INSERT
# -------------------------------------------
# BST RULE (structure that never change):
# - Left child < current node value
# - Right child > current node value
#
# Question 1: Smallest input?
# -> Node is none
#
# Question 2: What happens then?
# -> Create end RETURN a new node
#
# Question 3: How does it get smaller?
# -> We move done ONE level (left or right)
#
# Question 4: What stays the same?
# -> The BST ordering rule: left < node < right
#
# Question 5: What does the function return?
# -> A Tree node (the root of this subtree)
# -> Every recursive call MUST return a value
# ---------------------------------------------
class Tree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value, depth=0):
# STEP 1: SMALLEST possible input -> node is None
# STEP 2: Create and RETURN a new Tree node
# --------------
if node is None:
return Tree(value) # Base case
# STEP 3: RECURSION
# Decide whether to go LEFT or RIGHT
# The problem gets smaller because we move to a subtree
# --------------------
if value < node.value:
node.left = insert(node.left, value, depth + 1) # Insert into the left subtree
if value > node.value:
node.right = insert(node.right, value, depth + 1) # Insert into the right subtree
# STEP 4: STRUCTURE STAYS THE SAME
# STEP 5: RETURN VALUE
# ---------
return node
tree = insert(None, 50)
tree = insert(tree, 25)
tree = insert(tree, 33)
tree = insert(tree, 31)
def print_tree(node, depth=0):
if node is None:
return
print_tree(node.right, depth + 1)
print(" " * depth + str(node.value))
print_tree(node.left, depth + 1)
print_tree(tree)
# The tree is printed sideways
# ----------------------------
# 50
# 33
# 31
# 25
BST Populate
# BINERY SEARCH TREE - POPULATE
# ------------------------------
# Problem:
# Insert data into BST (each node in the correct position)
#
# Example:
# Input: [4, 2, 3, 1, 7, 6]
# Expected Output: [4 2 1 3 7 6]
#
# Goal:
# Insert values into a BST so that:
# - left subtree < node
# - right subtree > node
#
# Key idea:
# - We WALK DOWN the tree using recursion
# - We INSERT only when we find a None child
# - We RETURN existing nodes to preserve the tree
# -------------------------------------------------
items = [4, 2, 3, 1, 7, 6]
class Node:
def __init__(self, val):
self.info = val
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, val):
# BOOTSTRAP CASE:
# -------------------------------------------------------
# If the tree is empty, the first value becomes the root.
# No recursion needed here.
# -------------------------------------------------------
if self.root is None:
self.root = Node(val)
else:
# Otherwise, start walking the tree from the root
self.populate(self.root, val)
def populate(self, node, val):
# MOVE DOWN: LEFT SUBTREE
# -----------------------
if val < node.info:
# BASE CASE (ACTUAL INSERTION POINT)
# -------------------------------------
# We found an empty spot -> insert here
# -------------------------------------
if node.left is None:
node.left = Node(val)
# RECURSIVE STEP:
# -------------------------------------
# Left child exists -> keep walking down
# ---------------------------------------
else:
node.left = self.populate(node.left, val)
# MOVE DOWN: RIGHT SUBTREE
# ------------------------
if val > node.info:
if node.right is None:
node.right = Node(val)
else:
node.right = self.populate(node.right, val)
return node
# BUILD THE TREE
# --------------
tree = BinarySearchTree()
for x in items:
tree.insert(x)
# PREORDER TRAVERSAL OUTPUT
# -------------------------
def printTree(root):
if root is None:
return
print(root.info, end=" ")
printTree(root.left)
printTree(root.right)
printTree(tree.root)
# ------------------
# 4 2 1 3 7 6
# -------------------------------
# TESTING
# --------------------------------
def accumulate(root, output=None): # No mutable default argument (recommended)
if output is None:
output = []
if root is None:
return
output.append(root.info) # Insert value
accumulate(root.left, output) # Recursion
accumulate(root.right, output) # Recursion
return output
def populate(input):
tree = BinarySearchTree()
for x in input:
tree.insert(x)
return tree
# TEST / BALANCED INPUT
input = [4, 2, 3, 1, 7, 6]
tree = populate(input)
output = accumulate(tree.root)
assert output == [4, 2, 1, 3, 7, 6]
# TEST / NEGATIVE VALUES
input = [0, -10, 10, -20, -5, 5, 20]
tree = populate(input)
output = accumulate(tree.root)
assert output == [0, -10, -20, -5, 10, 5, 20]
# TEST / DUPLICATES
input = [4, 2, 4, 2, 3]
tree = populate(input)
output = accumulate(tree.root)
assert output == [4, 2, 3]
# TEST / RANDOM INSERTION ORDER
input = [8, 3, 10, 1, 6, 14, 4, 7, 13]
tree = populate(input)
output = accumulate(tree.root)
assert output == [8, 3, 1, 6, 4, 7, 10, 14, 13]
input = [9, 7, 8, 5, 6, 4, 3, 1]
tree = populate(input)
output = accumulate(tree.root)
assert output == [9, 7, 5, 4, 3, 1, 6, 8]
print("Tests passed")
