1

Input

sum_possible(2017, [4, 2, 10]) # -> False

Usage of any which causes RecursionError: maximum recursion depth exceeded

def sum_possible(amount, numbers, cache = None):
  if cache is None:
    cache = {}
  if amount in cache:
    return cache[amount]
  if amount == 0:
    return True
  if amount < 0:
    return False
  cache[amount] = any(sum_possible(amount - number, numbers, cache) for number in numbers)
  return cache[amount]

Usage of a for loop which solves the solution

def sum_possible(amount, numbers, cache = None):
  if cache is None:
    cache = {}
  if amount in cache:
    return cache[amount]
  if amount == 0:
    return True
  if amount < 0:
    return False
  
  for number in numbers:
    if sum_possible(amount - number, numbers, cache):
      cache[amount] = True
      return True
  
  cache[amount] = False
  return False
HeyZoos
  • 57
  • 1
  • 5

1 Answers1

3

The default recursion limit is 1000 calls. Although it's called a "recursion limit", it's actually the maximum depth of all nested function calls -- we just describe it in terms of recursion because it's hard to reach the limit without recursion -- you would need hundreds of different functions calling each other. The most common reason for exceeding the recursion limit is "infinite" recursion (e.g. failing to detect the base case properly).

In the version with a for loop, that allows 1000 recursive levels. Along with the cache, this is enough for your test case.

In the version that uses any(), the effective recursion limit is cut in half, because each recursive call is inside a call to any(). And this isn't enough.

Barmar
  • 741,623
  • 53
  • 500
  • 612
  • I think the answer could be made slightly easier to understand by stating explicitly that the so-called "recursion limit" is actually not directly related to "recursion", but more generally to **all function calls**, not just recursive function calls. In theory it would be possible to exceed it without any recursion, just by writing a very long line of `any(any(any(any(any(any(any(any(any(any(any(any(any(...` – Stef Nov 02 '21 at 15:48
  • @Stef I've updated the answer. I don't think nested calls like that would be a problem, because each call occurs after the previous one finishes, not while it's in progress. Also, `any()` doesn't return a sequence, so it can't be the argument to `any()`. – Barmar Nov 02 '21 at 15:54
  • *"I don't think nested calls like that would be a problem, because each call occurs after the previous one finishes, not while it's in progress. "* Uh. You're right of course. If it was a simpler function `f` called as `f(f(f(...)))` then that wouldn't add to the depth, because the arguments of a function are evaluated before the function is called. The reason the OP encountered this issue is because the recursive call is inside a generator-expression, not directly inside `any`. "Evaluating the generator-expression" doesn't have much effect except returning the generator. But then the – Stef Nov 02 '21 at 15:59
  • But then the calls to `sum_possible(amount - number, numbers, cache)` are evaluated while `any` has begun its evaluation, when `any` calls the generator's `.__next__`. So this issue is happening because of the generator, not because of `any`. It wouldn't happen if the OP had used a list comprehension instead of a generator expression: `any([sum_possible(amount - number, numbers, cache) for number in numbers])`. Although there would be another problem then: https://stackoverflow.com/questions/69773670/why-does-using-any-here-cause-this-program-to-hang-but-using-a-for-loop-doe – Stef Nov 02 '21 at 16:00
  • Exactly. And that's why we get two levels of call in the `any()` version -- `any()` is making the recursive calls itself. – Barmar Nov 02 '21 at 16:04