CODEWITHSUNDEEP
pythonrecursion
nom deplume
nom deplume

Reputation: 3

python recursion (why won't program exit once if condition is met?)

I am using the Euclidean algorithm to find the greatest common divisor of two numbers, using recursion.

I am confused because at some point the value of b will be equal to 0, at which point I have specified that the program return the value of a, which at this point should be the greatest common divisor.

The program does not do this. Instead, I was told that I need to put a return before the gcdRecur in the else step. But why would this be necessary, since the program should exit the if statement once b == 0? 

def gcdRecur(a, b):
    if b == 0:
        return a
    else:
        gcdRecur(b, a%b)
gcdRecur(60,100)

Upvotes: 0

Views: 730

Answers (2)

Martijn Pieters
Martijn Pieters

Reputation: 1123400

You are ignoring the return value of the recursive call:

else:
    gcdRecur(b, a%b)

Add a return there:

else:
    return gcdRecur(b, a%b)

A recursive call return value is not automatically passed on; it is just like any other function call, if you want the result to be passed back you need to do so explicitly.

Demo:

>>> def gcdRecur(a, b, _indent=''):
...     global level
...     print '{}entering gcdRecur({}, {})'.format(_indent, a, b)
...     if b == 0:
...         print '{}returning a as b is 0: {}'.format(_indent, a)
...         return a
...     else:
...         recursive_result = gcdRecur(b, a%b, _indent + ' ')
...         print '{}Recursive call returned, passing on {}'.format(_indent, recursive_result)
...         return recursive_result
... 
>>> gcdRecur(60,100)
entering gcdRecur(60, 100)
 entering gcdRecur(100, 60)
  entering gcdRecur(60, 40)
   entering gcdRecur(40, 20)
    entering gcdRecur(20, 0)
    returning a as b is 0: 20
   Recursive call returned, passing on 20
  Recursive call returned, passing on 20
 Recursive call returned, passing on 20
Recursive call returned, passing on 20
20

Upvotes: 1

Padraic Cunningham
Padraic Cunningham

Reputation: 180471

You need to actually return the value of the recursive call:

return gcdRecur(b, a%b)


def gcdRecur(a, b):
    if b == 0:
        return a
    else:
        return gcdRecur(b, a%b)

Upvotes: 3

Related Questions