Recursion: combo(4,3)

Contributed by Fran Trees
Drew University
Madison, New Jersey

Adapted from materials from the Carnegie Mellon University Summer Institute for AP CS (1983 or 84).

Materials
20-25 small cards (half of an index card is fine)
Overhead projector and screen
Transparency with combo permanently printed on it (see below)
Blank transparency to overlay on top of the combo transparency OR non-permanent marker

Problem
Evaluate combo(4,3)

Procedure

Have the cards readily available to give students who are called upon for help.
Project the combo method on the screen (as below).
Start the problem by saying: "(Principal's name) asked me to evaluate combo(4,3). Show the students a card that looks like this:

Principals Name
(4, 3)

Trace the code out loud: Let's see, combo(4,3)

amount is 4, value is 3
amount is not less than 0
value is not equal to 0 so I'll follow the else
amount is not equal to 0 so I'll follow the else
Hmmmm, I can't answer this question, I need help. Choose one student and give them a card with your name and combo(4,2) on it.

Your Name
(4, 2)

This must be evaluated as the computer would evaluate it.
You will be drawing the calling tree on the transparency as the calls are made. Keep it neat. Use a different color marker for answers returned.
It is important that with each call made, a blank card with the student's name (the name of the student making the call) with the call parameters is given to another student. No card is to be written on for more than one call and the cards are not to be discarded.
When an answer is reached (as in calls 4, 6, 8, 10) the student who was given that call to evaluate writes the answer on the card and returns the card to the person whose name is on the card.
Once a person gets a call with an answer on it (number 4 passes the answer 0 back to 3) indicating that the left addend in the addition expression has been evaluated, the person (number 3) makes the call to the right addend in the addition expression (gives number 5 a problem for which an answer is needed).
Now, number 3 only can give 2 a card with an answer after numbers 4 through 11 have finished their work!
An incomplete call tree is included below (with numbered calls to indicate the order in which the calls are made.
- Notice that numbers 7 and 13 call combo with the same parameters. The students will want to just get the answer from the previous work done. You do NOT allow them to do this. Remember, we are doing this as the computer does it!

Notes

If you are efficient doing this (helping the students along when needed), the left call for combo(4,3) can be completed in a 42-minute period with the debrief. I usually assign the completion of the right addend of the addition expression for homework.
Students may be called on more than once.

Debrief

When we finish the first half of the calling tree, I walk around and collect all of the cards that have been written on. We count how many calls were made to the method combo. This leads to an interesting and informative discussion about the efficiency of recursive algorithms.
Answer = 4

public static int combo(int amount, int value)
{
   if ((amount < 0) || (value == 0))
   {
     return 0;
   }
   else if (amount == 0)
   {
     return 1;
   }
   else
   {
     return ( combo(amount, value - 1)
	        + combo(amount - value, value    )  );
   }
 }

Recursion: combo(4,3)

Principals Name (4, 3)

Your Name (4, 2)

combo(4, 3)

Principals Name
(4, 3)

Your Name
(4, 2)