Finding recurrence for multiple return statements of different sizes

user_19258576 0
Viewed 155

I am kind of stuck on how to approach creating the recurrence for my piece of code, since we are going to have return statements that call the function twice or thrice, based on whether a stack has a blue plate. Any solution to this would be appreciated!

The Python code for the problem is shown below:

def stack_plates(n, color, has_blue_plate):
  if n == 0: 
    return 1

  if has_blue_plate:
    return stack_plates(n-1, 'Blue', True) + \
    stack_plates(n-1, 'Green', False)
  else:
    return stack_plates(n-1, 'Red', False) + \
    stack_plates(n-1, 'Blue', True) + \
    stack_plates(n-1, 'Green', False)
recurrence algorithm
1 Answers

Let's represent the stack as an array (left -to-right instead of bottom-to-top). We'll also use a "separator" (|) for ease of representation. Also, let the recursive function be count(n, c) where c represents the number of colors to use.

Consider a stack of n plates. Using | to mark the first blue plate in the stack, the arrangement could look like either of the following:

[ | (n-1)-length combination of B,G ]

[ (1)-length combination of R,G | (n-2)-length combination of B,G ]

[ (2)-length combination of R,G | (n-3)-length combination of B,G ]
...
[ (n-1)-length combination of R,G | ]

[ (n)-length combination of R,G ]

A few things to note here:

  1. The cases highlighted above don't intersect, since the separator is moved right by one position for each case.
  2. If you note the pattern, for valid x,y such that x+y = n-1, where x and y are the number of elements to the left and right of the separator respectively, the number of arrangements would be count(x,2) * count(y,2).
  3. Summing this over all arrangements, we get (count(0,2) * count(n-1,2)) + (count(1,2) * count(n-2,2)) + ... + (count(n-1,2) * count(0,2)) + (count(n,2))

Putting everything together, we get the following recurrence:

count(n,3) = count(n, 2) + summation of (count(x,2) * count(n-1-x,2)) for all x between [0, n-1]

Note: You can replace 3 and 2 with c and c-1 respectively to get a solution with c colors.

user_93507200
Related