python recursive function error RuntimeError: maximum recursion depth exceeded

Question

I have this script:

def number_of_occurences(c, message):
  position = message.find(c)
  if position == -1:
    return 0
  else:
    if len(message[position:]) == 0:
      return position
    else:
      return position + number_of_occurences(c, message[position:])

number_of_occurences('a', 'azertya')

But when I run it I get this error:

Traceback (most recent call last):
  File "frequency_analysis.py", line 31, in <module>
    number_of_occurences('a', 'azertya')
  File "file_name.py", line 29, in number_of_occurences
    return position + number_of_occurences(c, message[position:])
...
...
...
  File "file_name.py", line 29, in number_of_occurences
    return position + number_of_occurences(c, message[position:])
RuntimeError: maximum recursion depth exceeded

And I know about this similar question but it didn't help, it took longer time but gives the same error for this:

sys.setrecursionlimit(10000)

And this:

sys.setrecursionlimit(30000)

But for this:

sys.setrecursionlimit(50000)

it gives this error:

Segmentation fault (core dumped)

What am I doing wrong here? thanks in advance.

update:

Thanks to @abarnet here is the correct code:

def number_of_occurences(c, message):
  position = message.find(c)
  nbr = 0.0
  if position == -1:
    return 0
  else:
    nbr += 1
    if len(message[position:]) == 0:
      return nbr
    else:
      return nbr + number_of_occurences(c, message[position + 1:])

Is the problem (a) the recursion limit is too low because you need, say, 20000? (b) you thought the recursion depth in your code was way below any reasonable limit (like under 10)? (c) you know you're getting either infinite or way too deep recursion and want to know why your code is doing that? — abarnert, May 16 '13 at 00:16
If position equals zero, then you'll keep doing recursive calls. — dan, May 16 '13 at 00:17
Despite having some functional style primitives, Python lacks the tail call optimizations common in pure functional languages. Most of the time it is trivial to rewrite any recursive algorithm in a iterative way, which is the idiomatic form in Python. — Paulo Scardine, May 16 '13 at 00:18
@PauloScardine: That isn't the problem here. A correct version of this algorithm only needs a recursive depth of `len(message)`, which is well under the recursion limit. And transforming this incorrect version of the algorithm to an iterative form would just mean an infinite loop instead of infinite recursion. — abarnert, May 16 '13 at 00:19
@abarnert: that is why it is a comment and not an answer; I consider this to be a Python trap for newcomers and IMHO recursion should always be converted to iterative form in Python. — Paulo Scardine, May 16 '13 at 00:28
@PauloScardine: There are many good reasons to use recursion in Python, as long as you know the bounds. Even the stdlib uses it [all](http://hg.python.org/cpython/file/3.3/Lib/os.py#l422) [over](http://hg.python.org/cpython/file/cd9141a4f999/Lib/pickle.py#l407). — abarnert, May 16 '13 at 00:31

abarnert · Accepted Answer · 2013-05-16T00:26:07.700

The problem is that you recursively call yourself with the same parameters, which guarantees infinite recursion. It doesn't matter how high you set the recursion limit; you can't set it past infinity.*

Trace through it manually with your arguments.

position = message.find(c) # = 'azertya'.find('a') = 0
if position == -1: # Nope
else:
    if len(message[position:]) == 0: # len('azertya'[0:]) == len('azertya') == 7 != 0
    else:
        return position + number_of_occurences(c, message[position:])
            # 0 + number_of_occurences('a', 'azertya'[0:])
            # == 0 + number_of_occurences('a', 'azertya')
            # which is exactly what we were called with

Even if you don't start out with the first character, if you start out with any character in the string, you will eventually get to that point, and have the same problem. Again, try tracing through with 'r' instead of 'a'.

Running through an interactive visualizer like this one is a lot simpler than tracing manually (and prettier, and harder to screw up).

Alternatively, try printing out c, message, and position each time through, and it should be obvious what's going on.

The fix is really simple:

return position + number_of_occurences(c, message[position+1:])

* Even if you could, you'd get a segfault once the stack collides with the heap anyway, at least with CPython. That's why you got a segfault with only 50000. But even with a different implementation, like Stackless or PyPy, you'd get a memory error once there's no room for more stack frames. But if you had infinite bits of addressing and infinite virtual page table space so that weren't an issue, and were willing to wait forever… it still wouldn't work, but at least it would never fail.

python recursive function error RuntimeError: maximum recursion depth exceeded

update:

1 Answers1