Recursion program flow

Question

I have some textbook code that calls itself recursively. I don't understand the program flow. Here is the code:

def Recur_Factorial_Data(DataArray):

    numbers = list(DataArray)
    num_counter = 0

    list_of_results = []

    for num_float in numbers:

        n = int(num_float)

1.      result = Recur_Factorial(n)

        list_of_results.append(result)

def Recur_Factorial(num):

        if num == 1:
2.          return num
        else:
            result = num*Recur_Factorial(num-1)
3.         return result

        if num < 0:
            return -1
        elif num == 0:
            return 0
        else:
            return 0

In Recur_Factorial_Data, I loop through the data elements and call Recur_Factorial, which returns its value back to the calling function (Recur_Factorial_Data). I would expect that the lines marked 2 ("return num") and 3 ("return result") would always return a value back to the calling function, but that's not the case. For example, where the initial value (from the array DataArray) is 11, the function repeatedly calls itself until num is 1; at that point, the program falls to the line marked 2, but it does not loop back to the line marked 1. Instead, it falls through to the next line. The same happened on the line marked 3 -- I would expect it to return the result back to the calling function, but it does that in some cases and not in others.

I hope this is enough description to understand my question -- I just don't know why each return does not loop back to return the result to the calling function.

EDIT: The question at Understanding how recursive functions work is very helpful, and I recommend it to anyone interested in recursion. My question here is a bit different -- I asked it in the context of the program flow of the Python code where the recursive function is called.

Possible duplicate of [Understanding how recursive functions work](https://stackoverflow.com/questions/25676961/understanding-how-recursive-functions-work) — pjs, Feb 26 '18 at 01:29

Nikolay Lebedev · Accepted Answer · 2018-02-26T04:39:04.437

0

If it call itself recursively 10 times, it will be at the 10th level of recursion and should go back 10 times at the point where there was a recursive call with an intermediate result and only then exit from the recursive function to the place where it was called. Learn more about recursion

Also try to rearrange instructions in Recur_Factorial function in this way:

def Recur_Factorial(num):
    if num < 0:
        return -1
    elif num == 0:
        return 0
    elif num == 1:
        return num
    else:
        return num * Recur_Factorial(num-1)

edited Feb 26 '18 at 04:39

answered Feb 25 '18 at 22:46

Nikolay Lebedev

346
1
9

Thanks, Nikolay. That was helpful, but after substituting your code, I'm still not clear on one thing -- the first input value is 11. It calls itself recursively 10 times, each time decrementing the value of num until it reaches 1, where it stops at elif num == 1: return num. At that point, I would expect it to return to the calling function, but it does not -- it falls through to the next line (else: return num * Recur_Factorial(num-1)) where it calls itself recursively again. Why doesn't it return to the calling function to record the number 1 when it reaches the line elif num == 1? – RTC222 Feb 25 '18 at 23:49
1

Now I understand. It helps to watch the call stack. We push the RIP to the stack 10 times; on the 11th we reach the number 1, which is valid to return. At that point, the stack must be unwinded 10 times to return the correct answer for the factorial (39916800 in the case of factoral of 11). Thanks, Nikolay. – RTC222 Feb 26 '18 at 16:23
Correctly. Therefore deep recursion is dangerous. Each time you go to a deeper level, the size of the memory occupied by the call stack increases and you can get an exception. In Python you can set limit of recursion levels: `sys.setrecursionlimit(10000)` – Nikolay Lebedev Feb 26 '18 at 16:58

Recursion program flow

1 Answers1