Not Yet Answered # Recursion?

zeroliken 79 Discussion Starter pwolf 14 Gribouillis 1,313 Discussion Starter pwolf 14 Gribouillis 1,313 pyTony 888 Gribouillis 1,313 pyTony 888 OK, so HostGator for some reason no longer allows gcc/g++ access unless you have a Designated Server account, which is a lot of money to spend just to compile my "Hello World" program. Thus I figured I'd compile at home, then upload. Program is your regular old bare-bones Hello World ...

0

Is searching too hard for you?

If you have a problem understanding a concept you could post that here and thats where we come in and help you understand or clarify things.

*Edited 4 Years Ago by zeroliken*: n/a

0

Is searching too hard for you?

If you have a problem understanding a concept you could post that here and thats where we come in and help you understand or clarify things.

Sorry, i did look up some stuff and i think i get what its saying, but im doing these exercises on pyschools, and they want me to Write a recursive function power(x, y) to calculate the value of x raised to the power of y. I dont understand how to do this, or in this particular case, why?! There are many easier ways to do this.

0

It's not a real life program, it's an academic exercise. Basic recursion is related to the mathematical notion of 'induction formula'. Here the more obvious induction formula is that `x ** y = x * (x ** (y-1))`

. From this idea, you should be able to write a recursive function.

Also note that more efficient induction formulas exist for this: `x ** y = ((x ** z) ** 2) * (x ** r)`

if `y = 2 * z + r`

is the euclidian division of y by 2.

*Edited 4 Years Ago by Gribouillis*: n/a

0

I still dont understand, i read this:

http://openbookproject.net/thinkcs/python/english2e/ch11.html

And i cant understand the examples at all..

0

Alright, try to think algorithmically. Here is a pseudo code procedure to compute x raised to the power of y

```
to compute x raised to the power of y:
check that y is an integer >= 1
if y == 1:
return x
else:
compute x raised to the power of y - 1
multiply this result by x
return the result
```

This algorithm involves computing x raised to the power of (y - 1), that is to say the algorithm *calls itself recursively*.

Now let's translate this to python code. We are writing a function `power(x, y)`

which computes x raised to the power of y. The best way to understand the code is to use an *induction hypothesis* like in mathematics: we suppose that if y > 1, the call power(x, y-1) actually returns x raised to the power of y-1. Then we can write our function

```
def power(x, y):
if not(isinstance(y, (int, long))) or y < 1:
raise ValueError(("invalid value for power()", y))
if y == 1:
return x
else:
# the induction hypothesis is that power(x, y-1) returns x ** (y-1)
return x * power(x, y-1)
```

*Edited 4 Years Ago by Gribouillis*: n/a

0

I think, that we could include 0 as valid power, couldn't we?

If the power has fraction the recursion goes to negative so we could simplify the power ignoring the posibility of complex values (comparision will raise automatic error for complex power)

```
def power(x,y):
if y < 0:
raise ValueError('Power can not be negative or fractional: %s.' % y)
return 1 if not y else x*power(x, y-1)
```

Output:

```
>>> power(6,7)
279936
>>> 6**7
279936
>>> 0**0
1
>>> power(0,0)
1
>>> power(1,0)
1
>>> power(-4,2)
16
>>> power(4, 4j)
Traceback (most recent call last):
File "<pyshell#17>", line 1, in <module>
power(4, 4j)
File "<pyshell#8>", line 2, in power
if y < 0:
TypeError: unorderable types: complex() < int()
```

The binary version is not much more difficult (but does not function well for big exponents due to recursion limits in Python)

```
def power(x,y):
if y < 0:
raise ValueError('Power can not be negative or fractional: %s.' % y)
elif y == 1:
return x
elif y == 0:
return 0
else:
p = power(x, y//2)
return x*p*p if y & 1 else p*p
```

*Edited 4 Years Ago by pyTony*: n/a

0

I think, that we could include 0 as valid power, couldn't we?

Yes why not. Notice that 0**0 returns 1 in my python 2.7.

0

Binary verion had elif branches in wrong order and **0 wrong, here corrected:

```
def power(x,y):
if y < 0:
raise ValueError('Power can not be negative or fractional: %s.' % y)
elif y == 0:
return 1
elif y == 1:
return x
else:
p = power(x, y//2)
return x*p*p if y & 1 else p*p
assert power(6,7) == 6**7
assert power(0, 0) == 0**0
# () is a must in following **
assert power(-3432, 2) == (-3432)**2
```

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

I don’t want at this stage work on a big separate project as I've already got plenty ...

Hi. I have a form with list box : lst_product, datagridview : grd_order and button: btn_addline. lst_product has a list of product ids selected from database (MS Acess 2013) , grd_order is by default empty except for 2 headers and btn_addline adds rows to grd_order.

btn_addline :

`Private Sub btn_addline_Click(ByVal ...`