Converting an iterative solution to a recursive solution

Question

I'm currently working on a problem that requires I design a function that takes a string of '0's, '1's, and 'X's as an argument and returns a generator which yields the different combinations of the X's turned to 1's and 0's

ie: passing '0XX1', would return a generator that yields-> 0001, 0101, 0011, 0111,

I have solved the problem iteratively, but need to be able to able to solve it recursively. What is the best way to approach this type of problem? In a complex problem like this (well, complex to me!), how do I identify the base case and the recursive case?

Below is my iterative solution:

from typing import Generator
def binary_strings(string: str) -> Generator[str, None, None]:



    listOfIndices = []
    starterString = ''
    for index, char in enumerate(string):
    if char == 'X':
        starterString = starterString + '0'
        listOfIndices.append(index)

    else:
        starterString = starterString + char

    def stringGenerator(): #generates the different combos
    baseString = starterString
    moddedString = ''
    n = len(listOfIndices)
    counter = 1

    for i, character in enumerate(
            starterString):
        if i == 0:
            yield starterString
        else:
            break

    while counter <= n:

        for i, chara in enumerate(baseString):
            if i in listOfIndices:
                moddedString = baseString[:i] + '1' + baseString[i + 1:]
                yield moddedString
                counter += 1
                if counter > n and n >= 1:
                    counter = 1
                    n -= 1
                    baseString = moddedString
                    break
                else:
                    continue

return stringGenerator()

It is a recursion problem. I first solved it iteratively because I reasoned I'd be able able to more easily identify a recursive solution (I was wrong- now I'm stumped!). — Cjk
– Cjk, Commented Feb 24, 2020 at 1:36
I would prefer not to, so I can really begin to grasp this type of problem conceptually and practically. — Cjk
– Cjk, Commented Feb 24, 2020 at 1:43
Does this answer your question? What are reasonable ways to improve solving recursive problems? — AMC
– AMC, Commented Feb 24, 2020 at 2:14

Mark · Accepted Answer · 2020-02-24 01:45:02Z

1

It's often the case that recursive functions are easier to reason about and shorter. Typically you'll start with a base case. Here you can imagine what your function should yield with an empty string. Probably ''.

Next if your first character is not an X you just yield that first character plus the result of recursively calling the rest. If it is and X then you yield both 1+recursive call and 0+recursive call. Something like:

def combos(s):
    if len(s) == 0:
        yield  ''
        return 

    head, *tail = s
    for combo in combos(tail):
        if head == 'X':
            yield '1'+ combo
            yield '0'+ combo
        else:
            yield head + combo

s = '0XX1'
list(combos(s))

#['0111', '0011', '0101', '0001']

answered Feb 24, 2020 at 1:45

Mark

92.7k8 gold badges116 silver badges156 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Cjk Over a year ago

wow, that is a lot shorter! thanks for the assist. It's making more sense to me now

Scott Hunter · Accepted Answer · 2020-02-24 01:17:39Z

0

Ignoring the (trivial) base case (that is, where there are no X's to replace), binary_strings(s) = binary_strings(s') + binary_strings(s'') where s' is s with the first X replaced with a 0, and s'' is s with the first X replaced with a 1.

answered Feb 24, 2020 at 1:17

Scott Hunter

50k12 gold badges64 silver badges107 bronze badges

Collectives™ on Stack Overflow

Converting an iterative solution to a recursive solution

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related