J.B94 - 5 months ago 10x

Python Question

I have two recursive statements that do the same thing, i understand how the first one works but I am confused on the second case.

1)

`def recurPower(base, exp):`

'''

base: int or float.

exp: int >= 0

returns: int or float, base^exp

'''

# Base case is when exp = 0

if exp <= 0:

return 1

# Otherwise, exp must be > 0, so return

# base* base^(exp-1). This is the recursive case.

return base * recurPower(base, exp - 1)

this first case although it is recalling itself it still leaves a variable "base" behind to multiply every time around the method.

2)

`def recurPowerNew(base, exp):`

'''

base: int or float.

exp: int >= 0

returns: int or float; base^exp

'''

# Base case is when exp = 0

if exp <= 0:

return 1

# Recursive case 1: exp > 0 and even

elif exp % 2 == 0:

return recurPowerNew(base*base, exp/2)

# Otherwise, exp must be > 0 and odd, so use the second

# recursive case.

return base * recurPowerNew(base, exp - 1)

In this case I don't understand how it works if it is an

do parameters return a value if there is no body in the method?

Answer

Let's take an example:

```
print recurPowerNew(3, 4)
```

so `base`

is 3 and `exp`

is 8. This will fall into the case you are concerned with, and call:

```
return recurPower(9, 2)
```

... which will also fall into the same case, and call

```
return recurPower(81, 1)
```

ah-ha! This is the odd case. So this will call:

```
return 81 * recurPower(81, 0)
```

The second term of the multiplication is 1, so we return 81 all the way up the stack. If you follow this through, it also works for numbers that are not powers of two.

The point of this, is that it is *much* more efficient than the first method. It will produce one or two stack frames per bit of the exponent. The first method will produce `exponent`

stack frames!

Source (Stackoverflow)

Comments