Lecture 9:

Branching Recursion

CS 136: Spring 2024

Katie Keith

• Lab 3: Recursion, released
• Start early! Use pen and paper!
• During Labs this week: 1-on-1 feedback /grading for Lab 2
• Required lab attendance
• If you are not present (without an excused absence) I will not be able to grade your lab and you will not receive credit.

📣 Announcements

• Practice branching recursion problems
• Last 10 minutes: Quiz recap and Nick Handford (Director, Quantitative Skills Programs)

🎯 Today’s Learning Objectives

📚Readings

• Sedgewick & Wayne. CS:IA. Section 2.3.

Why is recursion important in CS 136?

Looking ahead, we will use recursion throughout CS 136.

1. Recursive data structure: Linked Lists
2. Implementing tree traversal and graph traversal
3. When we implement Divide and Conquer Algorithms (Merge Sort or Quick Sort)

Figure credit: Wikipedia

Review: Recursive Euclid’s algorithm

public static int recursiveGcd(int p, int q){

if(q == 0){

return p;

else{

return recursiveGcd(q, p % q);

}

}

​

1. What is the base case?
2. What is the recursive step?
3. Draw the manual trace tree for mystery("gates").
4. What is this method trying to do?

public static String mystery(String s){

int strLen = s.length();

​

if(strLen <=1){

return s;

}

​

String a = s.substring(0, strLen/2);

String b = s.substring(strLen/2, strLen);

return mystery(b) + mystery(a);

}

JavaDocs for substring

​

💡Think-pair-share

Board work

TPS1.java

💻

Branching recursion

Often, we see a pattern in recursive algorithms in which each recursive call branches into one or more recursive calls, forming a tree-like structure of calls.

public static String mystery(String s){

int strLen = s.length();

​

if(strLen <=1){

return s;

}

​

String a = s.substring(0, strLen/2);

String b = s.substring(strLen/2, strLen);

return mystery(b) + mystery(a);

}

Example:

Task: Making change

Suppose we have an infinite supply of coins in different denominations.

Let’s write a program to count the number of ways to make change for an input amount using the given coin denominations.

Example

int[] coins = {1, 2, 5}; // denominations of the coins

// (but recall, we have an infinite supply of them)

int amount = 6; // amount to make change for

Number of ways to make change:

• Way 1: 6 x {1}
• Way 2: 4x{1} and 1x{2}
• Way 3: 2x{1} and 2x{2}
• Way 4: 3x{2}
• Way 5: 1x{1} and 1x{5}

This question is asking about combinations (not permutations) since order does not matter

Tips for branching recursion problems

1. For each element, think if you can make a branching binary decision
• Running Example:
• The coin denomination 2 is not included or
• The coin denomination 2 is included
2. Sometimes it can be helpful to work backwards from the end goal
• Running Example: Let’s subtract from the total amount when we include a coin. We’ll try to get to total amount equal to 0.
3. Use a helper function with additional arguments
• Running Example: In our helper function, we’ll add an argument to keep track of which denomination we’re looking at (which index in the array)

CoinChange.java

💻

public static int helper(int[] coins, int amount, int index) {

if (amount == 0) {return 1;}

​

if (amount < 0 || index == coins.length) {return 0;}

​

int includeCurrentCoin = helper(coins, amount - coins[index], index);

int excludeCurrentCoin = helper(coins, amount, index + 1);

​

return includeCurrentCoin + excludeCurrentCoin;

}

​

Draw the recursive call tree for this example. In the end, what does ways equal?

int[] coins = {1, 2};

int amount = 3;

int ways = helper(coins, amount, 0);

​

💡Think-pair-share

• Define branching recursion problems
• Practice reading recursive code

✅

✅

🎯 Today’s Learning Objectives