4 ms·
This code terminates only if all child-problems eventually are found not to have subproblems. So either it has infinite subproblems or it returns true. So recur
by hughdbrown 3y ago
This code terminates only if all child-problems eventually are found not to have subproblems. So either it has infinite subproblems or it returns true. So recursion is good for a use case unless the problem decomposes into infinite subproblems, but in that case this test function never returns false.
Makes more sense to do it as breadth-first with only one return value:
from collections import deque
def isRecursionOk(problem):
q = deque(problem)
while q:
problem = q.popleft()
q.append(list(breakDownIntoSubProblems(problem)))
return true