This Week's Worksheet ⬇️

mentor04.pdf

mentor04_sol.pdf

Useful Resources / Related Practice Problems

• SP21 Tree Recusion slides

  07-Tree_Recursion.pdf.pdf

• Practice Problems

Steps for writing a recursive function

1. Create base case(s)

2. Reduce your program to smaller subproblem

   → "When would the program terminate?"

   → "if else cases"

3. Recursive call

Real world analogy for recursion

You are in a line and want to know how many people are in front of you. How to figure this out?

• Base case: When would you stop counting? → when there's no one at the front
• Subproblems: If there's still a person in front → 1+ recursion

Linear recursion in practice

def sum_squares(N):
		""" Return the sum of K**2 for K from 1 to N (inclusive)."""
		if N < 1:
				return 0
		else:
				(return sum of K**2 for K from 1 to N-1 + N**2)
		==> return sum_squares(N - 1) + N**2

Recursion Practice

1. Write a function is_sorted that takes in an integer n and returns true if the digits of that number are nondecreasing from right to left.

   def is_sorted(n):
         """
         >>> is_sorted(2)
         True
         >>> is_sorted(22222)
         True
         >>> is_sorted(9876543210)
         True
         >>> is_sorted(9087654321)
         False
         """
   			# Your Code Here
   

   Observations:

   • (Toggle to check)

   Formally think of the problem:

   • (Toggle to check)

   Putting all these together

   • (Toggle to see solution)