Unable to explain recursions-CodePudding

I am struggling to understand the behaviour of the python interpreter when it comes to recursive functions.

The following code failed and produced the unexpected result (0,1,2,3,4,5,5,4,5,5,3,4,5....):

def recur(num):
    while num < 6:
        print(num)
        num =1
        recur(num)

recur(0)

Making the function return solved the issue (1,2,3,4,5)

def recur(num):
    while num < 6:
        print(num)
        num =1
        return recur(num)

recur(0)

It make sense that without return the original function is not terminated when initializing the new call however I am unable to explain the flow that led to the results.

Thanks!

CodePudding user response：

Adding the return inside the while loop just ensures the loop only loops one iteration. For recursion you don't actually need the loop (the recursion is the loop), which only serves to make things confusing. You need a condition that stops the recursions and a recursive call:

def recur(num):
    if num < 6:         # base condition
        print(num)
        recur(num   1)  # recursive call

recur(0)

prints:

Obviously if you want to print starting at 1, you can call recur(1).

CodePudding user response：

To explain your original output (0,1,2,3,4,5,5,4,5,5,3,4,5....):

The first 6 entries (0,1,2,3,4,5) are created by the initial recursion. You print one value, then recurse with the next higher value. At 6 your recursion ends without printing a value (the while loop is not entered).

At this point you return to the function that printed 5 and is now holding the value 6 (because it incremented before recursing). The function stops its while loop, returns. Then you go to the function that originally had the number 4. It had its value incremented to 5. Therefore it loops around, prints 5, increments to 6, then recurses. Does nothing, returns.

The function that originally got 4 is now at 6, and returns to the function that originally got 3 and is now holding 4. So now the recursion continues for 4 and 5, then returns all the way back to the function originally receiving 2, now holding 3, and so on and on.

In other words, if you only count recursions down, the values are produced in the following groups: (0,1,2,3,4,5), (5,), (4,5), (3,4,5), ...)

(Note: I'm sloppy with my terminology. When I say return to a function, what I mean is return to a stack frame of the recursive function. I hope I have not confused you further).