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