-1

I have biuld a function in python that replicates a circuit of three other functions (defined in the main function) that call eachother while iterating over a given list of numbers required in the main function (In the code there is a way to break out of the recursion circuit). Basically this structure:

def main_function(list_of_numbers, parameter_1, parameter_2):

    def block1():
        nonlocal result_1, result_2, var_1, var_2, var_3
        # Code
        block2()

    def block2():
        nonlocal result_1, result_2, var_1, var_2, var_3
        # Code
        if b:
            # Code
            block2()
        else:
            # Code
            block3()

    def block3():
        nonlocal result_1, result_2, var_1, var_2, var_3
        # Code
        if a:
            # Code
            bloc1()
        else:
            # Code
            if b:
                # Code
                if b:
                    # Code
                    if c:
                        # Code
                        block1()
                    else:
                        block2()
                else:
                    block2()
            else:
                block3()

    result_1 = []
    result_2 = []
    var_1 = 0
    var_2 = 0
    var_3 = 0
    block1()
    return result_1, result_2

The problem I'm having is that if the list of numbers is larger than 500 values then this error appears:

RecursionError: maximum recursion depth exceeded in comparison

I know I can change the limit of recursion but what does that mean, is my computer gonna be affected if I want to operate a list of half a million values?. The code inside the functions is quite simple and short.

Daniel Casasampera
  • 351
  • 7
  • 20
  • I don't see any break conditions in bloc2() and bloc3(). What you are using is indirect recursion. The point is to call a function2 from another function1 and vice versa. The issue is, there is a chance that you may end up in an infinite loop once you enter bloc2() since you are calling bloc2() again. Similarly for bloc3. What I would recommend is handling that specific edge case. Else just make sure you are jumping to another funciton instead of the same. – Akshay Sehgal Nov 21 '20 at 22:40
  • Similar question: https://stackoverflow.com/questions/8177073/python-maximum-recursion-depth-exceeded – Óscar López Nov 21 '20 at 22:41
  • Does this answer your question? [What is the maximum recursion depth in Python, and how to increase it?](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it) – Bill Huang Nov 21 '20 at 22:41
  • In languages without tail recursion optimization, it's usually not recommended to use recursion when iteration would be more efficient. – Barmar Nov 21 '20 at 22:42
  • Okey so in the code there are break conditions that is why it works when I try it in small lists. The issue is not so much on how to set the limit higher but rather what are the implications. Also trying to write it in form of iteration doesnt seem obvious to me. – Daniel Casasampera Nov 21 '20 at 22:55

1 Answers1

1

A function is recursive if it calls itself either directly or via some other function that it calls. While recursion is a useful way to build an algorithm it can be a resource hog. Each time the function is called, it creates some local state (the local variables) and memory space remains in use until the function finally returns. If your recursive calls go a million deep, that's a million local frames in memory.

The risk is that recursion will blow up the stack frame or process memory and you will get a hard failure of the code. This is a really bad error as the entire program exits with no ability to clean up. Even if the program doesn't crash, it uses a lot of memory, impacting the rest of your system. There could be more swapping and worse case, the Linux oom killer could randomly kill processes in an attempt to get resources for the kernel.

To mitigate risk from either accidental recursion or a buggy algorithm that doesn't properly limit itself, python puts a limit on recursion. But developers can override that limit via sys.setrecursionlimit(some_huge_number) in which case anything bad is on their heads.

tdelaney
  • 73,364
  • 6
  • 83
  • 116
  • Could it be possible to tell python that the only variables needed are those defined in the main function; and to overwrite and forget previous recursion actions?? – Daniel Casasampera Nov 21 '20 at 23:00
  • 1
    You are kind of doing that with the `nonlocal` declaration so the recursive functions have small function objects. But there is still a C level stack frame and a python function object per call that you can't get rid of - basically because each called function returns into that context when done. The good news is that these are pretty small so you can go rather deep (am I vague enough?!). – tdelaney Nov 21 '20 at 23:21
  • Nice, as far as I understand python isnt being as inneficient as it could be, so that means I can savely increase the recursion limit, is that right? (Sorry for the vagueness, Ive studied algorithms and numerical problems i gneneral but I have very little knoledge in computing and coding) – Daniel Casasampera Nov 22 '20 at 00:07
  • 1
    Yes, and one thing you can do is monitor memory usage on a test to see how much is consumed by any given iteration. Its best for recursive algorithms to be self-limiting in some manner (maybe a global variable with your own count). But generally and especially with python where the base function frame is significant, deep recursion is problematic. Personally, I avoid it. – tdelaney Nov 22 '20 at 00:15