Overflowed stack in recursion python3 code

Question

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.

Good question, I learned a lot from this i.e. I Googled, read, understood, fixed, thought,wrote. — hygull
– hygull, Commented Dec 18, 2018 at 1:38

Blckknght · Accepted Answer · 2018-12-18 00:47:55Z

2

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.

answered Dec 18, 2018 at 0:47

Blckknght

106k11 gold badges135 silver badges188 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Gagantous Over a year ago

where should i placed the sys.setrecursionlimit ? inside its function ? above function name ? or below main ?

Gagantous Over a year ago

okay, i have set the limit, and it works fine!. is there any other way rather increasing the heap limit of recursion ? like improving the code ? or something else? Because, when i set other value, lets say, print(pangkat(13,100000)), it gave me a Segmentation fault (core dump)., even i have set the recursion limit to sys.setrecursionlimit(2000000000). I have tried print(pangkat(13,100000)) with two other code and it works just fine.

Blckknght Over a year ago

Well, the way to improve the code is to make it non-recursive, as you've done in your other two example implementations of the function. Recursion is not the best tool for many problems. And for some problems it's really bad, so bad that it can't actually be used to solve the problem at all in a practical sense.

Community · Accepted Answer · 2020-06-20 09:12:55Z

1

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

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Dec 18, 2018 at 1:27

hygull

8,7282 gold badges47 silver badges55 bronze badges

2 Comments

Gagantous Over a year ago

okay, i have set the limit, and it works fine!. is there any other way rather increasing the heap limit of recursion ? like improving the code ? or something else? Because, when i set other value, lets say, print(pangkat(13,100000)), it gave me a Segmentation fault (core dump)., even i have set the recursion limit to sys.setrecursionlimit(2000000000). I have tried print(pangkat(13,100000)) with two other code and it works just fine.

hygull Over a year ago

The solution would be to set the max recursion depth dynamically by introducing a new function as a start point with signature like trigger(nilai, pangkatnilai, limit). Inside that the first line would be sys.setrecursionlimit(limit) and after that you can write a return statement as return pangkat(nilai, pangkatnilai). 2nd option would be to use iteration, the safe approach. 3rd option would be to find another approach to get the result.

Collectives™ on Stack Overflow

Overflowed stack in recursion python3 code

2 Answers 2

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related