In recursive functions do we need to return the function explicitly in the body?

Question

I was instructed to find gcd using the Euclid method. I initially wrote the following in Python:

def gcdRecur(a,b):
    if b==0:
        print('I am here')
        return a
    else:
        gcdRecur(b,a%b)
        print(a,b)

print(gcdRecur(51,187))

The result was:

I am here
34 17
51 34
187 51
51 187
None

I had no idea why its output is the way it is, then I realised looking at others code that one is to use the return statement explicitly.

def gcdRecur(a,b):
    if b==0:
        print('I am here')
        return a
    else:
        return gcdRecur(b,a%b)
        print(a,b)


print(gcdRecur(51,187))

I got

I am here
17

So I got what I wanted and learnt that we should use return statement rather then just calling the function.

My question is why is the output of the first code reversed? And why does the following code work even though no return statement is used

def tower(n,fr,to,spare):
    if n==1:
        print_move(fr,to)
    else:
        tower(n-1,fr,spare,to)
        tower(1,fr,to,spare)
        tower(n-1,spare,to,fr)

The above code is what I learnt in MIT course on edX, it is solution to Tower of Hanoi problem.

Here the code works fine. So when I want the implementation in reverse order we call the recursive function directly and in correct order we use a return statement, am I right?

Answer 1

My question is why is the output of the first code reversed?

It is not really reversed in the strict sense, but I think I get what you mean. You perhaps expect that the "parent" call prints before the "child" call.

If we however inspect the code, we see that:

def gcdRecur(a,b):
    if b==0:
        print('I am here')
        return a
    else:
        gcdRecur(b,a%b)  # make child call
        print(a,b)       # print from the parent call

If you would have swapped the two, it would print in what you probably call the "right way":

def gcdRecur(a,b):
    if b==0:
        print('I am here')
        return a
    else:
        # swap printing and recursive calls
        print(a,b)       # print from the parent call
        gcdRecur(b,a%b)  # make child call

If you use a return statement however, the function is terminated from the moment it reaches a return, so if we print things after the return statement is reached, that printing never happens. In case we want that, we could for instance use a try-finally construct.

More in depth, if we "trace" a program, for example with (this is not valid Python code, it is more to give an insight into how these calls are handled):

gcdRecur(51,187)
    if 187 == 0:  # fails
    else:  # we take the else branch
        gcdRecur(187,51)
            if 51 == 0:  # fails
            else:  # we take the else branch
                gcdRecur(51,34)
                    if 51 == 0:  # fails
                    else:  # we take the else branch
                        gcdRecur(34,17)
                            if 51 == 0:  # fails
                            else:  # we take the else branch
                                gcdRecur(17,0)
                                    if 0 == 0:  # succeeds!
P                                       print('I am here')
                                        return 17
P                               print(34,17)
P                       print(51,34)
P               print(187,51)
P       print(51,187)

I here marked the lines that print with a P at the left. As you can see, the lines with P are in the same order.