CODEWITHSUNDEEP
pythonrecursionpython-2.7
Yahya KACEM
Yahya KACEM

Reputation: 2481

python recursive function error RuntimeError: maximum recursion depth exceeded

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:])

Upvotes: 2

Views: 12690

Answers (1)

abarnert
abarnert

Reputation: 365717

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.

Upvotes: 5

Related Questions