Last active
December 12, 2015 06:28
-
-
Save brookskindle/4728857 to your computer and use it in GitHub Desktop.
Two recursive methods for finding the value of x raised to the nth power. The first method uses the more straight forward approach, but upon inspecting the algorithm, we see that it ends up taking a LOT more recursive calls than power1 does.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def power(x, n): | |
| if (n): | |
| return x * power(x, n - 1) | |
| else: | |
| return 1 | |
| def power1(x, n): | |
| if (not n): #0th power | |
| return 1 | |
| elif (n % 2 == 0): #power is even | |
| return power1(x, n / 2) * power1(x, n / 2) | |
| else: #power is odd | |
| return power1(x, int(n / 2)) * power1(x, int(n / 2)) * x |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment