Bug with returning a value from recursive function

Question

This was written in answer to a leetcode problem: given a string, return the minimum number of cuts needed to partition the string into palindrome substrings.

It may not be the most efficient way, but I decided to explore the possibilities as a graph, the idea being to only add nodes that can possibly be in a path that creates palindromic substrings. As I build the graph level by level, all I need to do is track which level I am on (0 for root (i.e. the original string), 1 for children of root and so on), and once I hit a node whose value is a palindrome, the current level is the required answer.

The bug I am getting is that instead of returning the level, I get a return value of None. The bug only occurs for some inputs. I have tried entering different inputs but cannot see a pattern nevermind determining the cause. Via debugging I know that the return statement is being executed when expected. Why is this happening? What is the problem?

class Node:
    def __init__(self, val='', children=None):
        self.val = val
        self.children = children if children else []

class Solution:
    def minCut(self, s: str) -> int:
        if s == s[::-1]:
            return 0
        
        def _create_graph(root, level):
            n = len(root.val)
            for i in range(1, n):
                substr = root.val[:i]
                if substr == substr[::-1]:
                    comp_of_substr = root.val[i:]
                    if comp_of_substr == comp_of_substr[::-1]:
                        return level # code is reaching here as expected, but None is being returned
                    child = Node(comp_of_substr)
                    root.children.append(child)
            for child in root.children:        
                _create_graph(child, level + 1)
            
        root = Node(s)
        return _create_graph(root, 1)

I have made sure the code is reaching the return value and terminating there. A sample of the debug I did by print statements:

root.val='abccbc', num_cuts=1
n=6
    i=1
    substr='a'
        comp_of_substr='bccbc'
        child.val='bccbc' appended to root.val='abccbc' children
    root.children = ['bccbc']
    i=2
    substr='ab'
    root.children = ['bccbc']
    i=3
    substr='abc'
    root.children = ['bccbc']
    i=4
    substr='abcc'
    root.children = ['bccbc']
    i=5
    substr='abccb'
    root.children = ['bccbc']
root.val='bccbc', num_cuts=2
n=5
    i=1
    substr='b'
        comp_of_substr='ccbc'
        child.val='ccbc' appended to root.val='bccbc' children
    root.children = ['ccbc']
    i=2
    substr='bc'
    root.children = ['ccbc']
    i=3
    substr='bcc'
    root.children = ['ccbc']
    i=4
    substr='bccb'
        comp_of_substr='c'
            found solution with num_cuts=2 # the print statement that gave this is literally
                                           # above the 'return level'

In for child in root.children: you are ignoring the returned level from the recursive call, and below that loop you are exiting the function without returning anything (i.e None) — trincot
– trincot, Commented Aug 7, 2021 at 13:39
@trincot That was my first guess, but when I debugged it I printed out what the args immediately at the beginning of the recursive function, e.g. root.val='bccbc', num_cuts=2. The last such printout was the expected one, so I thought that meant I was not calling the function more than I needed. Are you able to give an answer with how to correct this please? EDIT - I just counted the number of calls to the recursive function, it was indeed 2 as expected. — msm1089
– msm1089, Commented Aug 7, 2021 at 13:49
"That was my first guess, but...": This is not a guess. You get None because of this. I didn't analyse your function any further. If you don't want None, you will have to have a return statement in the case the first for loop does not execute the return you have there. This is not about printing, but about returning. You can print what you want, but if you don't return it, you'll get None. — trincot
– trincot, Commented Aug 7, 2021 at 13:56
@trincot Thanks, I added the missing line. I still don't see how the bug is caused by what you said. I confirmed that the recursive function is only running twice. I first did it by printing (I know the difference between printing and returning!). As another check after your first comment, I added a property to the Solution class that incremented every time the recursive function was called. I'm not saying you are wrong, but I do not understand why the cause of the bug is what you say. Could you provide some amended code that will fix the issue you mention? — msm1089
– msm1089, Commented Aug 7, 2021 at 14:18
I will not answer based on your code, because I don't believe this brute force algorithm will finish within the time limits, even when corrected. But just look at your code as it is and ask your self: What will this function return when the first for loop finishes and comes to the second for loop? Can you point to the line of code where it returns anything? It just isn't there. There isn't a return statement there. — trincot
– trincot, Commented Aug 7, 2021 at 14:23

Mulan · Accepted Answer · 2021-08-07 17:20:12Z

1

Generators are a good use case for problems involving combinations and permutations. This is because we can easily get a partial or complete answer without needed to modify the search/traversal program. Below we write palindromify as a generator which finds all combinations of substrings palindromes -

def palindromify(s, w = ""):
  if not s: return
  if not w and is_palindrome(s): yield (s,)
  yield from palindromify(s[1:], w+s[0])
  if w and is_palindrome(w):
    for p in palindromify(s, ""):
      yield (w, *p)

This demonstrates another fundamental programming practice: When you have a complex problem, you can make it easier to solve by solving several smaller sub-problems. Checking whether a particular string is a palindrome is a different task than breaking a string into palindrome substrings. Let's write is_palindrome as its own function -

def is_palindrome(s):
  return len(s) < 2 or s[0] == s[-1] and is_palindrome(s[1:-1])

Let's see the output of palindromify on your input -

for p in palindromify("abccbc"):
  print(p)

('a', 'bccb', 'c')
('a', 'b', 'cc', 'b', 'c')
('a', 'b', 'c', 'cbc')
('a', 'b', 'c', 'c', 'b', 'c')

And here it is with a slightly bigger input -

for p in palindromify("abbadeeda"):
  print(p)

('abba', 'deed', 'a')
('abba', 'd', 'ee', 'd', 'a')
('abba', 'd', 'e', 'e', 'd', 'a')
('a', 'bb', 'adeeda')
('a', 'bb', 'a', 'deed', 'a')
('a', 'bb', 'a', 'd', 'ee', 'd', 'a')
('a', 'bb', 'a', 'd', 'e', 'e', 'd', 'a')
('a', 'b', 'b', 'adeeda')
('a', 'b', 'b', 'a', 'deed', 'a')
('a', 'b', 'b', 'a', 'd', 'ee', 'd', 'a')
('a', 'b', 'b', 'a', 'd', 'e', 'e', 'd', 'a')

And with a palindrome as input -

for p in palindromify("racecar"):
  print(p)

('racecar',)
('r', 'aceca', 'r')
('r', 'a', 'cec', 'a', 'r')
('r', 'a', 'c', 'e', 'c', 'a', 'r')

You can see even a small string can yield many possible combinations. And so using a generator here is important because we can terminate the computation as soon as we get the first result. Since the algorithm is written to return the largest palindromes first, it should result in the fewest cuts -

def solve(s):
  for p in palindromify(s):
    return len(p)-1

Above return automatically halts palindromes and no computations happen beyond the first result, potentially saving significant time and space. Now let's see solve called on our example inputs -

print(solve("abbadeeda")) # 2
print(solve("abccbc")) # 2
print(solve("racecar")) # 0
print(solve("abcde")) # 4
print(solve("z")) # 0

edited Aug 7, 2021 at 17:20

answered Aug 7, 2021 at 17:12

Mulan

136k35 gold badges240 silver badges276 bronze badges

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

2 Comments

msm1089 Over a year ago

Thanks @Mulan, I like the approach. Unfortunately it does not seem to work for all inputs, e.g. "aaabaa" it returns 2, instead of 1. I modified it to keep track of the minimum partitions, but of course that meant generating all of them and took too long. Question: I get the first 2 lines of palindromify, but what does yield from do as opposed to just yield? Also you mentioned that the largest palindromes should be found first, but for the failure case "aaabaa", the smallest partitioning comes around the middle of the generated solutions. I'm going to try using DP now.

Mulan Over a year ago

I was worried there would be some inputs where solve fails. yield from ... is a way to pass delegation of the generator to another generator; it's what enables you to write recursive generators. notice how yield outputs a value where as yield from ... is always before another iterable expression. If I get some time later, maybe I'll try to fix it :D

Collectives™ on Stack Overflow

Bug with returning a value from recursive function

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related