Can you explain this difference of recursion depth in Python using these seemingly equivalent functions?

Question

I noticed that on my machine, the following reaches the max recursion depth for n = 2960:

m = {0:0, 1:1}
def f(n):
    if n not in m:
        m[n] = f(n - 1) + f(n - 2)
    return m[n]

while this version reaches it for n = 988:

m = {0:0, 1:1}
def f(n):
    if n not in m:
        m[n] = sum(f(n - i) for i in [1, 2])
    return m[n]

Can anyone explain what happens "under the hood" that explains such difference?

More precisely, it would be very nice to understand why the factor is 3 in this example and be able to derive it for summations with more terms.

It sounds like there are two extra function calls on the stack for each recursive call. Calling `sum()` accounts for one extra stack frame. My guess is that `sum()` performs another function call internally, or perhaps evaluating the generator expression takes an additional stack frame. It could be the [`PyIter_Next` call here](https://hg.python.org/cpython/file/57c157be847f/Python/bltinmodule.c#l2334). — John Kugelman, Apr 10 '23 at 01:29
@JohnKugelman No, `sum()` does not perform another function call internally, but it's the generator expression that makes that extra function. Switch the generator expression to a list comprehension and that extra function is removed: `sum([f(n - i) for i in [1, 2]])` — blhsing, Apr 10 '23 at 01:48
@JohnKugelman the generator expression accounts for at least one of those. it literally makes a function object (a generator function) and then calls it, look at a `dis.dis("(x for x in range(10))")` — juanpa.arrivillaga, Apr 10 '23 at 01:50
@blhsing well, no, a list comprehension *also* uses a function. — juanpa.arrivillaga, Apr 10 '23 at 01:50
@juanpa.arrivillaga Perhaps I worded it imprecisely. I meant that by using a list comprehension the extra function call is not performed simultaneously with the call of `sum()`, i.e. the list comprehension function is removed from the call stack before the call of `sum()`. — blhsing, Apr 10 '23 at 01:52
A follow-on from this question: https://stackoverflow.com/q/75979676/674039 — wim, Apr 12 '23 at 18:24

wim · Answer 1 · 2023-04-10T03:15:47.633

18

TL;DR: sum is an extra function call, and the generator expression it is summing over is also implemented with a nested function scope (docs)

... the comprehension is executed in a separate implicitly nested scope. This ensures that names assigned to in the target list don’t “leak” into the enclosing scope.

Therefore the second way uses two extra stack frames during the recursion, as well as the recursive call itself, which is explaining the factor of 3 here.

Note that the default recursion limit is 1000, so you should really be seeing the stack overflow at exactly 1000 for the first case, and at 334 for the second case (on Python 3.10 or lower). To get 2960 and 988 here, you may have:

imported something which called sys.setrecursionlimit(3000), and
spent a few stack frames already, somewhere.

Running this code within an IDE or a tricked-out interactive REPL, for example, will likely have done both of the above.

Interesting recent developments:

There is PEP 709 – Inlined comprehensions which is all about removing this hidden function from comprehensions. Generator expressions are currently not inlined in the reference implementation for the PEP, although it may be considered in future.

CPython 3.11 already has some optimizations to reduce the number of function calls in this code, which changes the point of stack overflow. It will happen at 501 instead of 334 in CPython 3.11. The reason is described in the changelog at What’s New In Python 3.11: Inlined Python function calls.

edited Apr 10 '23 at 03:15

answered Apr 10 '23 at 02:59

wim

338,267
99
616
750

"Generator expressions are currently not inlined in the reference implementation for the PEP, although it may be considered in future." - even then, generator inlining would be restricted to cases where the generator isn't exposed to other functions, like `[x for x in (i**2 for i in l) if x < 1000]`. Passing the generator to `sum` would prevent inlining. – user2357112 Apr 10 '23 at 03:32
Awesome info! However, I don't think `sum` is to blame for the extra function call, and I'd appreciate your input. If you look at the call stacks I posted in my answer, `sum` is nowhere to be found. Also, arguments to a function are evaluated before the function is invoked. If you replace `sum` with some user-defined function `g` (in which you can add log statements), you'll notice `g` never gets invoked, since the recursion limit is hit while evaluating the arguments to `g`. – rpm Apr 10 '23 at 15:28
@rpm: `sum` is nowhere to be found because it's written in C, and C functions don't show up in Python stack traces. Nevertheless, it really is on the stack. While the argument to `sum` is indeed evaluated before calling `sum`, evaluating a generator expression just produces a generator object. It doesn't actually run the code. The generator object's stack frame is entered each time `sum` requests a value from the generator object (and the stack frame is exited when the generator object yields a value to `sum`). – user2357112 Apr 10 '23 at 16:36
@rpm To put it simply, evaluating the function arguments does not consume the generator. The generator's frame must be kept around until it is done. – wim Apr 10 '23 at 16:47
@user2357112 @wim Ah thanks! You're both definitely right about generator expressions returning a generator object. However, there's still some unexplained behavior here. Try replacing `sum` with `(lambda x: next(x) + next(x))` (expressed as an IIFE here to fit it on one line). We now see `` in the call stack, but there are still *n* unaccounted-for functions in the call stack, where *n* is roughly equal to the number of `` in the call stack. – rpm Apr 10 '23 at 16:53
1

@rpm `next` is also a function call – wim Apr 10 '23 at 17:01
1

@rpm: And expanding on wim's point, `next` is a *C* function, so like `sum`, it doesn't show up in the stack trace. – user2357112 Apr 10 '23 at 18:59
@user2357112 understood, but if both `sum` and `next` are C functions that are being invoked at every invocation of `f`, then the ratio of `f` invocations to total functions on the call stack would be 1:4 (for every invocation of `f`, there is one invocation each of `f`, `sum`, ``, and `next`). However, what we observe is a ratio of 1:3. – rpm Apr 10 '23 at 19:05
1

@rpm: `sum` does not call `next`. It uses `PyIter_Next` directly, which does not count towards the recursion limit (though it does take stack space). – user2357112 Apr 10 '23 at 19:08

rpm · Answer 2 · 2023-04-10T02:08:40.457

I'll add my debugging here as well. After running some tests, I found that the traceback module was giving me a call stack that was significantly (~333) less than the recursion limit. I noticed that this difference was always close to the number of <genexpr> invocations on the call stack:

import sys
import traceback
from collections import Counter
from pprint import pprint

sum_every_n = int(sys.argv[1])

def f(n=0):
    try:
        if n % sum_every_n == 0:
            return sum(f(n+i) for i in [1,2])
        else:
            return f(n+1) + f(n+2)
    except RecursionError:
        stack = traceback.extract_stack()
        counts = Counter([frame.name for frame in stack])

        stack_size = len(stack)
        stack_size_plus = stack_size + counts['<genexpr>']

        pprint(counts)
        print(f'rec limit:      {sys.getrecursionlimit()}')
        print(f'stack size:     {stack_size}')
        print(f'adj stack size: {stack_size_plus}')
        sys.exit()

f()

Here are the results for some values of sum_every_n:

$ ./rec3.py 1
Counter({'f': 333, '<genexpr>': 332, '<module>': 1})
rec limit:      1000
stack size:     666
adj stack size: 998

$ ./rec3.py 2
Counter({'f': 499, '<genexpr>': 249, '<module>': 1})
rec limit:      1000
stack size:     749
adj stack size: 998

$ ./rec3.py 3
Counter({'f': 599, '<genexpr>': 200, '<module>': 1})
rec limit:      1000
stack size:     800
adj stack size: 1000

$ ./rec3.py 4
Counter({'f': 665, '<genexpr>': 166, '<module>': 1})
rec limit:      1000
stack size:     832
adj stack size: 998

It seems that the generator is indeed adding a function call to the stack, but also that each generator expression counts as two functions on the call stack. This explains the ratio in your original question. Not sure why this is the case though, and I welcome any possible explanations!

Caridorc · Answer 3 · 2023-04-10T01:51:14.980

A fascinating behavior, I did not get to the root of the issue but I still would like to share some logging code that I wrote that might help others find the issue:

m = {0:0, 1:1}
def f(n, depth=0):
 print(f"{'  '*depth}f({n})")
 if n not in m:
  print(f"{'  '*depth}Computing f({n-1}) + f({n-2})")
  m[n] = sum(f(n - i, depth+1) for i in [1, 2])
 else:
  print(f"{'  '*depth}Already computed f({n})")
 return m[n]

print("Testing the version with the iterator, call stack is:")
f(10)

m = {0:0, 1:1}
def g(n, depth=0):
 print(f"{'  '*depth}g({n})")
 if n not in m:
  print(f"{'  '*depth}Computing g({n-1}) + g({n-2})")
  m[n] = g(n - 1, depth+1) + g(n - 2, depth+1)
 else:
  print(f"{'  '*depth}Already computed g({n})")
 return m[n]

print("Testing the version with the normal sum, call stack is:")
g(10)

The output is:

Testing the version with the iterator, call stack is:
f(10)
Computing f(9) + f(8)
  f(9)
  Computing f(8) + f(7)
    f(8)
    Computing f(7) + f(6)
      f(7)
      Computing f(6) + f(5)
        f(6)
        Computing f(5) + f(4)
          f(5)
          Computing f(4) + f(3)
            f(4)
            Computing f(3) + f(2)
              f(3)
              Computing f(2) + f(1)
                f(2)
                Computing f(1) + f(0)
                  f(1)
                  Already computed f(1)
                  f(0)
                  Already computed f(0)
                f(1)
                Already computed f(1)
              f(2)
              Already computed f(2)
            f(3)
            Already computed f(3)
          f(4)
          Already computed f(4)
        f(5)
        Already computed f(5)
      f(6)
      Already computed f(6)
    f(7)
    Already computed f(7)
  f(8)
  Already computed f(8)
Testing the version with the normal sum, call stack is:
g(10)
Computing g(9) + g(8)
  g(9)
  Computing g(8) + g(7)
    g(8)
    Computing g(7) + g(6)
      g(7)
      Computing g(6) + g(5)
        g(6)
        Computing g(5) + g(4)
          g(5)
          Computing g(4) + g(3)
            g(4)
            Computing g(3) + g(2)
              g(3)
              Computing g(2) + g(1)
                g(2)
                Computing g(1) + g(0)
                  g(1)
                  Already computed g(1)
                  g(0)
                  Already computed g(0)
                g(1)
                Already computed g(1)
              g(2)
              Already computed g(2)
            g(3)
            Already computed g(3)
          g(4)
          Already computed g(4)
        g(5)
        Already computed g(5)
      g(6)
      Already computed g(6)
    g(7)
    Already computed g(7)
  g(8)
  Already computed g(8)

So they look to be doing the exact same thing... my Python version is 3.8.15, You should try running this code to see if the output is the same also with your Python version.

On my Python version, I hit the recursion limit for f(333) and g(997)

Edit: thanks to John Kugelman I am getting closer to the answer, with the code:

import time
import inspect

m = {0:0, 1:1}
def f(n, depth=0):
    # fraction part of time
 print(f"{'  '*depth}f({n})")
 if n not in m:
  print(f"{'  '*depth}Computing f({n-1}) + f({n-2})")
  m[n] = sum(f(n - i, depth+1) for i in [1, 2])
 else:
  print(f"{'  '*depth}Already computed f({n})")
 print(f"{'  '*depth}Returning {m[n]}")
 print(f"{'  '*depth}Call stack has length {len(inspect.stack())} and is: {[x.function for x in inspect.stack()]}")
 return m[n]

print("Testing the version with the iterator, call stack is:")
start = time.time()
f(10)

m = {0:0, 1:1}
def g(n, depth=0):
 print(f"{'  '*depth}g({n})")
 if n not in m:
  print(f"{'  '*depth}Computing g({n-1}) + g({n-2})")
  m[n] = g(n - 1, depth+1) + g(n - 2, depth+1)
 else:
  print(f"{'  '*depth}Already computed g({n})")
 print(f"{'  '*depth}Returning {m[n]}")
 print(f"{'  '*depth}Call stack has length {len(inspect.stack())} and is: {[x.function for x in inspect.stack()]}")
 return m[n]

print("Testing the version with the normal sum, call stack is:")
g(10)

import sys
print(sys.version)

The output is:

Testing the version with the iterator, call stack is:
f(10)
Computing f(9) + f(8)
  f(9)
  Computing f(8) + f(7)
    f(8)
    Computing f(7) + f(6)
      f(7)
      Computing f(6) + f(5)
        f(6)
        Computing f(5) + f(4)
          f(5)
          Computing f(4) + f(3)
            f(4)
            Computing f(3) + f(2)
              f(3)
              Computing f(2) + f(1)
                f(2)
                Computing f(1) + f(0)
                  f(1)
                  Already computed f(1)
                  Returning 1
                  Call stack has length 20 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
                  f(0)
                  Already computed f(0)
                  Returning 0
                  Call stack has length 20 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
                Returning 1
                Call stack has length 18 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
                f(1)
                Already computed f(1)
                Returning 1
                Call stack has length 18 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
              Returning 2
              Call stack has length 16 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
              f(2)
              Already computed f(2)
              Returning 1
              Call stack has length 16 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
            Returning 3
            Call stack has length 14 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
            f(3)
            Already computed f(3)
            Returning 2
            Call stack has length 14 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
          Returning 5
          Call stack has length 12 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
          f(4)
          Already computed f(4)
          Returning 3
          Call stack has length 12 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
        Returning 8
        Call stack has length 10 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
        f(5)
        Already computed f(5)
        Returning 5
        Call stack has length 10 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
      Returning 13
      Call stack has length 8 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
      f(6)
      Already computed f(6)
      Returning 8
      Call stack has length 8 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
    Returning 21
    Call stack has length 6 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
    f(7)
    Already computed f(7)
    Returning 13
    Call stack has length 6 and is: ['f', '<genexpr>', 'f', '<genexpr>', 'f', '<module>']
  Returning 34
  Call stack has length 4 and is: ['f', '<genexpr>', 'f', '<module>']
  f(8)
  Already computed f(8)
  Returning 21
  Call stack has length 4 and is: ['f', '<genexpr>', 'f', '<module>']
Returning 55
Call stack has length 2 and is: ['f', '<module>']
Testing the version with the normal sum, call stack is:
g(10)
Computing g(9) + g(8)
  g(9)
  Computing g(8) + g(7)
    g(8)
    Computing g(7) + g(6)
      g(7)
      Computing g(6) + g(5)
        g(6)
        Computing g(5) + g(4)
          g(5)
          Computing g(4) + g(3)
            g(4)
            Computing g(3) + g(2)
              g(3)
              Computing g(2) + g(1)
                g(2)
                Computing g(1) + g(0)
                  g(1)
                  Already computed g(1)
                  Returning 1
                  Call stack has length 11 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
                  g(0)
                  Already computed g(0)
                  Returning 0
                  Call stack has length 11 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
                Returning 1
                Call stack has length 10 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
                g(1)
                Already computed g(1)
                Returning 1
                Call stack has length 10 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
              Returning 2
              Call stack has length 9 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
              g(2)
              Already computed g(2)
              Returning 1
              Call stack has length 9 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
            Returning 3
            Call stack has length 8 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
            g(3)
            Already computed g(3)
            Returning 2
            Call stack has length 8 and is: ['g', 'g', 'g', 'g', 'g', 'g', 'g', '<module>']
          Returning 5
          Call stack has length 7 and is: ['g', 'g', 'g', 'g', 'g', 'g', '<module>']
          g(4)
          Already computed g(4)
          Returning 3
          Call stack has length 7 and is: ['g', 'g', 'g', 'g', 'g', 'g', '<module>']
        Returning 8
        Call stack has length 6 and is: ['g', 'g', 'g', 'g', 'g', '<module>']
        g(5)
        Already computed g(5)
        Returning 5
        Call stack has length 6 and is: ['g', 'g', 'g', 'g', 'g', '<module>']
      Returning 13
      Call stack has length 5 and is: ['g', 'g', 'g', 'g', '<module>']
      g(6)
      Already computed g(6)
      Returning 8
      Call stack has length 5 and is: ['g', 'g', 'g', 'g', '<module>']
    Returning 21
    Call stack has length 4 and is: ['g', 'g', 'g', '<module>']
    g(7)
    Already computed g(7)
    Returning 13
    Call stack has length 4 and is: ['g', 'g', 'g', '<module>']
  Returning 34
  Call stack has length 3 and is: ['g', 'g', '<module>']
  g(8)
  Already computed g(8)
  Returning 21
  Call stack has length 3 and is: ['g', 'g', '<module>']
Returning 55
Call stack has length 2 and is: ['g', '<module>']
3.8.15 (default, Nov 24 2022, 15:19:38) 
[GCC 11.2.0]

So the problem is that the generator expression is getting put on the call stack, taking up space that could be used by the actual recursive function. Now it would be interesting to investigate why the generator expression is getting put on the stack as if it were a function.

"Now it would be interesting to investigate why the generator expression is getting put on the stack as if it were a function" A generator expression evaluates to a generator object. This is done by creating a generator function, calling it, and returing the generator object. Generators work has coroutines. Iteration over the generator object requires the generator function execution frame. — juanpa.arrivillaga, Apr 10 '23 at 02:58

score 1 · Answer 4 · answered Apr 10 '23 at 14:33

The cause of the difference in recursion depth is the use of a generator expression.

A question with a star:

Why does the following allow the stack to be at least 2x deeper, in comparison to the first case, which is an almost identical definition:

m={0:0, 1:1}
def f(n):
   if n not in m:
      m[n] = f(n-2)+f(n-1)
   return m[n]

Answering this question can help you understand memoization better.

Can you explain this difference of recursion depth in Python using these seemingly equivalent functions?

4 Answers4

Interesting recent developments:

Linked