Recursion?

[pwolf]

Hello, could someone explain recursion to me?
It would be much appreciated!

[zeroliken]

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.

[pwolf]

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.

[Gribouillis]

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.

[pwolf]

I still dont understand, i read this:
http://openbookproject.net/thinkcs/python/english2e/ch11.html
And i cant understand the examples at all..

[Gribouillis]

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)

[TrustyTony]

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

[Gribouillis]

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.

[TrustyTony]

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