CODEWITHSUNDEEP
python-3.xrecursion
Gagantous
Gagantous

Reputation: 518

Overflowed stack in recursion python3 code

I tried to build a simple code that solved square operational with value n using python, plus, i want to learn recursion. I made three different style code like below syntax:

First code 

def pangkat(nilai, pangkat):
    a = int(1)
    for i in range(pangkat):
        a = a * nilai
    return a

if __name__ == "__main__":
    print(pangkat(13, 8181))

Second Code

def pangkat(nilai, pangkat):
    hasil = nilai**pangkat
    return hasil

if __name__ == "__main__":
    print(pangkat(13, 8181))

Third Code

def pangkat(nilai, pangkatnilai):
    if pangkatnilai == 1:
        return nilai

    return nilai * pangkat(nilai, pangkatnilai-1)

if __name__ == "__main__":
    print(pangkat(13,8181))

Note : param nilai as number that will be raised, and pangkat as number that will raised param nilai), all of these code works well for example, when i fill the nilai and param

Input 0

pangkat(13, 12)

Output 0

23298085122481

The problem occurred when i changed the param pangkat >= 1000, it will said , it will gave me an error but only in third code.

Traceback (most recent call last):
  File "pang3.py", line 8, in <module>
    print(pangkat(13,1000))
  File "pang3.py", line 5, in pangkat
    return nilai * pangkat(nilai, pangkatnilai-1)
  File "pang3.py", line 5, in pangkat
    return nilai * pangkat(nilai, pangkatnilai-1)
  File "pang3.py", line 5, in pangkat
    return nilai * pangkat(nilai, pangkatnilai-1)
  [Previous line repeated 995 more times]
  File "pang3.py", line 2, in pangkat
    if pangkatnilai == 1:
RecursionError: maximum recursion depth exceeded in comparison

While the first and second code works well. What could go wrong with my recursion function ? plus i need the explanation for it, Thanks!

NB : As possible, is there any better approach for using recursion like i needed ? i build my recursion using my own logic, so i expect if someone had better approach for that code.

Upvotes: 1

Views: 105

Answers (2)

hygull
hygull

Reputation: 8730

Actually the default max depth for recursion is 1000. To get rid of that issue in this case you have to use the below 1 line at the top of your code.

sys.setrecursionlimit(1002)

It would be better to set to max value if you are also looking to try other values e.g. 1050,1400 etc. (It is also valid in your case).

sys.setrecursionlimit(1500)

Visit https://docs.python.org/3/library/sys.html#sys.setrecursionlimit to check the details. Here I am pasting the important part to be focused.

  • Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.

  • The highest possible limit is platform-dependent. A user may need to set the limit higher when they have a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

  • If the new limit is too low at the current recursion depth, a RecursionError exception is raised.

import sys

print(sys.getrecursionlimit()) # 1000
sys.setrecursionlimit(1002)    # Set max depth for recursion
print(sys.getrecursionlimit()) # 1002 (Checing again) 

def pangkat(nilai, pangkatnilai):
    if pangkatnilai == 1:
        return nilai

    return nilai * pangkat(nilai, pangkatnilai-1)

if __name__ == "__main__":
    print(pangkat(13, 1000))

Upvotes: 1

Blckknght
Blckknght

Reputation: 104852

The Python interpreter limits how deeply you can recurse. By default, the depth is 1000 levels of function calls, after which you get an exception (the RecursionError you see from your third function). So in one respect, your code is working as expected. You wanted to recurse 8181 times and Python quit after 1000, since that's the default limit.

If you want to recurse more deeply, you can change the recursion limit, using the sys.setrecursionlimit function. Setting the recursion limit to 9000 would be enough for your function to run with the argument you were giving it in your example.

As for why Python only allows a limited depth of recursion, it's mostly because there's seldom a need for more. Recursion is much less efficient than iteration in most situations, so you generally don't want to use deep recursion for big problems, as it will be very slow. Most of the time that you hit the recursion limit, it will be because of a bug that made what was supposed to be a shallow recursion into an infinite recursion, and Python did the right thing by stopping the program rather than letting it go on forever.

Upvotes: 2

Related Questions