Skip to main content
Have students use a recursive algorithm to solve the problem of only eating the squares of a chocolate bar that contain nuts to introduce recursive algorithms for arrays.
- Here is the pseudocode for the recursive algorithms students should use to solve the only eating chocolate squares with nuts in them problem:
Eat Chocolate Bar(B)
if B is a single square then
else
Break the bar into two pieces
Eat Chocolate Bar(Piece 1)
Eat Chocolate Bar(Piece 2)
- If the student is passed a single square with nuts, they will eat it and make no recursive call to a neighbor.
- If the student breaks the chocolate bar into two pieces, they can pass each piece to a different neighbor so they can each execute the algorithm themselves.
- The associated programming problem is obtained by using an array to represent a one-dimensional chocolate bar.
- Pseudocode for searching through the array:
const MAX = 100;
type BarType = array[1..MAX] of Boolean;
procedure EatChocolate( Bar: BarType; Low, High: Integer);
var Middle: Integer;
begin
if Low = High then
begin
if Bar[Low] then
writeln(’Eating nut at: ’, Low)
end
else
begin
Middle := (Low + High) div 2;
EatChocolate(Bar, Low, Middle);
EatChocolate(Bar, Middle+1, High)
end
end {EatChocolate};
- Once students understand the programming problem, the stage is set for them to recursive algorithms involving arrays, such as computing Fibonacci numbers or a binary search.