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.

Share 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. with FacebookShare 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. with Twitter
  • 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
          if B has a nut then
            Eat it
        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.

Tags

External Source
"Recursion: From Drama to Program" by Mordechai Ben-Ari.
Other Tips By
Other Tips By Mordechai Ben-Ari