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

Principals Name
(4, 3)

Your Name
(4, 2)

Notes Debrief
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    )  );
   }
 }

combo(4, 3)