Breaking out of a recursive loop in python-CodePudding

I've used a recursive loop to find path between words formed by one-letter changes. For example:

MAN-->CUT

The recursive function uses while to look at the one-letter neighbors of a word and find the neighbor that is most like the goal word. Then using that word it goes deeper, up to a depth of two more than the letter difference between the start and goal word. (This seems to be sufficient for most cases, although proving this is a whole other matter)

The problem is my recursive function is giving me trouble. At first I just tried to use a "break" but the recursion would keep running after. So, I searched here for methods to fix that issue. To save you reading all of the classes and functions I've made I created a stripped down version that produced the same error.

def recurse(c):
  try:
    while c>0:
      print(c)
      c-=1
      if c==5:
        raise StopIteration

      recurse(c-1)
                  
  except StopIteration:
    print("We found the word. Stop the recursion.")
  
  
recurse(12)

If you run this code the exception will be raised multiple time and the recursion won't stop. I read about this method using exceptions to stop a recursion in its tracks in another post here, but the case of use was a bit different.

Have I implemented this incorrectly?

CodePudding user response：

The problem you're having is that while break (or an exception that you can't outside the loop, but within the same function) can only break out of the single loop, not the whole chain of loops that exist in the recursive call stack.

The second version of your code that you put in an answer works because the exception breaks out of all of the recursive functions, since that's how exceptions bubble up through the call stack. The downside is that you need to catch the exception at the top level (a helper function might do this for you more elegantly).

But an alternative design approach would be to change the recursion up a little bit. Rather than either returning on failure (e.g. no solution found) or raising an exception (that will be caught at the top level) on success, you could return a value that indicates success or failure, and check that value to see if you could keep looping and/or recursing in the function.

Try something like:

def recurse(c):
    while c>0:
        print(c)
        c-=1
        if c==5:
            return True

        result = recurse(c-1)
        if result:
            return result

    return False

I'd note that this particular recursive function doesn't make a whole lot of sense since the loop and the recursion are both manipulating the same c value, but it's possible that's an artifact of your simplification of the problem and that the two flow control mechanisms make more sense in your real problem.

CodePudding user response：

I thought about what it was that I wanted to "stop" not the "while" but rather the initial call of a the recursion that started all the trouble. So I realized this was the solution:

def recurse(c):

    while c>0:
      print(c)
      c-=1
      if c==5:
        raise StopIteration

      recurse(c-1)
                  
 

try:
 recurse(12)
except StopIteration:
  print("Stop the recursion I want to get off.")

I'm happy it's now working and simply writing up this question helped me solve my own problem. Although, I suspect it's not the most elegant soliton. For example I choose that error code because it "sounded right" -- is it being used correctly here?

CodePudding user response：

Instead of exception you can use break statement
https://www.tutorialspoint.com/python/python_break_statement.htm

def recurse(c):
    while c>0:
        print(c)
        c-=1
        if c==5:
            break

        recurse(c-1)