Python filling a 2D list with recusion
Question: I need to create a program that will recursively fill a 2D list. The list
forms a grid like

    
    
    I - I - I - - - 
    I I - - - - - - 
    I I I I - - - - 
    

Then the user input column and row numbers. The program then fills that
section of "-" with "@". So if row = 1 and column = 4 it would look like:

    
    
    I - I @ I @ @ @
    I I @ @ @ @ @ @
    I I I I @ @ @ @ 
    

I have to do this with recursion. The only thing I could get it to do was
partially fill a row. Please help me.


Answer: The program is pretty simple if you start from bottom right of the grid and
recurse backwards till (0, 0). Let's walk through the logic step by step:

  * We start from bottom right, in your case (2, 7). And you need to fill everything that is greater than your bounds, in your case (0, 3). These are the parameters we will need for the recursive method.
    
        recur_fill(input_list, a, b, i, j)
    

  * We begin with the boundary conditions. Your program needs to execute only while the co-ordinates are greater than zero. i.e., if `i < 0` or `j < 0` we have to stop. This translates to:
    
        if i < 0 or j < 0:
        return
    

  * Now, we need to take care of the paint bounds, namely a and b. As long as our co-ordinates are greater than your bounds, we need to check if the cell has `-` and fill it with `@`. Which translates to:
    
        if i >= a and j >= b:
        if input_list[i][j] == '-':
            input_list[i][j] = '@'
    

  * Now, we need to fill the cells recursively till all the cells that fall within our conditions are filled. i.e.,
    
        recur_fill(input_list, a, b, i - 1, j)
    recur_fill(input_list, a, b, i, j - 1)
    

Summing these, we have:

    
    
    from pprint import pprint
    
    def recur_fill(input_list, a, b, i, j):
        if i < 0 or j < 0:
            return
    
        if i >= a and j >= b:
            if input_list[i][j] == '-':
                input_list[i][j] = '@'
    
        recur_fill(input_list, a, b, i - 1, j)
        recur_fill(input_list, a, b, i, j - 1)
    
    def main():
        input_list = [['I', '-', 'I', '-', 'I', '-', '-', '-' ],
                      ['I', 'I', '-', '-', '-', '-', '-', '-' ],
                      ['I', 'I', 'I', 'I', '-', '-', '-', '-' ]]
        recur_fill(input_list, 0, 2, 2, 7)
        pprint(input_list)
    
    
    if __name__ == '__main__':
        main()
    

