Counting block combinations

I am given the following problem : A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square. There are exactly seventeen ways of doing this.

How many ways can a row measuring fifty units in length be filled?

Here's what I've wrote so far in python:



Can someone please explain to me how this recursive function works please. I've been studying recursive function and I understood how it works.The problem is that I cannot understand how the speffic one works.

I haven't yet solved #114. You've made interesting comments: "The program you wrote that you don't understand."


The program would be easier for me to read if the variable names corresponded to the problem description, block and row. I could refactor to please myself...


These conditions terminate the recursion. The second says "if this is already solved use the cached answer".

if(colorsize>blocksize): return solutions
if(cache[blocksize] != 0): return cache[blocksize]



for position in range(0,blocksize-colorsize+1):

describes all the places a block could be inserted (by "left edge")



for blocklength in range(colorsize,blocksize-position+1):

are the lengths of red blocks that would fit.



solutions+=prob(blocksize-position-blocklength-1,colorsize)

Note that the recursion depends on both iteration variables, position and blocklength. In other words, the number of solutions is the number of ways to get populate to here plus the number of ways to populate the remaining of the space after sticking in said red block at said position.



I hope this didn't help.