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
– abarnert, Commented May 16, 2013 at 0:16
If position equals zero, then you'll keep doing recursive calls. — dan
– dan, Commented May 16, 2013 at 0: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
– Paulo Scardine, Commented May 16, 2013 at 0:18

abarnert · Accepted Answer · 2013-05-16 00:26:07Z

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.

Collectives™ on Stack Overflow

python recursive function error RuntimeError: maximum recursion depth exceeded

update:

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

update:

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related