Beginner - Recursion

[blazahjazz]

Hello, I'm a high school student and I just started learning Python.
I'd really appreciate some help on some problems I've been assigned, and some tips that could help me out in the future with problems like these.

>>> getLeaves ( jenny )
[5,3,0,9]
>>>
>>> getLeaves ( joshua )
[15,17,19,11,13]

Find all length n strings of Xs and Os without consecutive Os. Hint: find the length (n-1) strings and attach an add'l X or O when you can. map and filter might be useful. The order doesn't matter.

>>> xox(0)

>>>
>>> xox(1)

>>>
>>> xox(2)

>>>
>>> xox(3)

>>>
>>> xox(4)

Thanks!

[griswolf]

All recursion is basically the same: Solve a big problem by splitting it into smaller problems that you solve by splitting them into smaller problems that... eventually are so small that you just do the work and return. To make it a recursive problem, the method for solving each sub problem is the same as the method for all sizes (except, maybe, the smallest).

Think about it like this:
If I can solve the problem for a very few items
And I can make any larger problem smaller in a way that lets me solve it by combining the smaller solutions with the current state
Then I can find a recursive solution to the problem.

Here's one solution for the Xs and Os problem

def xo(remaining,prefixes):
  if remaining == 0:
    return prefixes
  xs = [p+'X' for p in prefixes]
  os = [p+'O' for p in prefixes if 'X' == p[-1]]
  return xo(remaining-1,xs+os)

print 0, xo(0,['X','O'])
print 1, xo(1,['X','O'])
print 2, xo(2,['X','O'])
print 3, xo(3,['X','O'])

"""outupt
0 ['X', 'O']
1 ['XX', 'OX', 'XO']
2 ['XXX', 'OXX', 'XOX', 'XXO', 'OXO']
3 ['XXXX', 'OXXX', 'XOXX', 'XXOX', 'OXOX', 'XXXO', 'OXXO', 'XOXO']
"""

[TrustyTony]

Here is generator solution:

def xox(n):
    if n==0: yield ''
    elif n==1:
        yield 'X'
        yield 'O'
        
    else:
        for start in xox(n-1):
            if not start.endswith('O'): yield start+'O'
            yield start+'X'
    
print 'xox(5) = ',list(xox(5))

['XOXOX', 'XOXXO', 'XOXXX', 'XXOXO', 'XXOXX', 'XXXOX', 'XXXXO', 'XXXXX', 'OXOXO', 'OXOXX', 'OXXOX', 'OXXXO', 'OXXXX']

[TrustyTony]

elif is unnecessary in my function, n==0 case is enougn.

Can you make the function save once calculated values to dictionary and first find them before calling itself recursively?

Can you make function with for loop until n without recursion with same logic as this generator?

[griswolf]

Very nice tonyjv.