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

Question

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)

Padraic Cunningham · Accepted Answer · 2015-01-25 17:50:58Z

3

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)

answered Jan 25, 2015 at 17:50

Padraic Cunningham

181k30 gold badges264 silver badges327 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Martijn Pieters · Accepted Answer · 2015-01-30 11:49:13Z

1

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

edited Jan 30, 2015 at 11:49

answered Jan 25, 2015 at 17:51

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

1 Comment

nom deplume Over a year ago

Thank you, the print statements were helpful to see exactly where the program was operating at any point in time.

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related