Print the results
- Algorithms course
- Beginner
- Lesson 52/80
- 4 min
Print the power and combination results.
Add fast power
In the final step we add fast_power(base, exp). It runs in O(log n) by halving via squaring when exp is even.
If exp even: base^exp = (base^2)^(exp/2). If exp odd: base * base^(exp-1). This halves the number of calls.
Project complete
You now have a recursive calculation application: power computes power, combination computes combination, print_results prints, fast_power does fast power.
Each function was built on the previous one. You learned the power of recursion and cumulative code.
Practice Fast power
Write fast_power(base, exp). If exp=0 return 1, if exp even fast_power(base*base, exp//2), else base * fast_power(base, exp-1). Print 1024 with print(fast_power(2, 10)).
Starter code
def power(base, exp):
# Compute power
if exp == 0:
return 1
return base * power(base, exp - 1)
def combination(n, k):
# Compute combination
if k == 0 or k == n:
return 1
return combination(n - 1, k - 1) + combination(n - 1, k)
def print_results():
# Print results
print(power(2, 5))
print(combination(5, 2))
def fast_power(base, exp):
# Fast powerSample solution
def power(base, exp):
# Compute power
if exp == 0:
return 1
return base * power(base, exp - 1)
def combination(n, k):
# Compute combination
if k == 0 or k == n:
return 1
return combination(n - 1, k - 1) + combination(n - 1, k)
def print_results():
# Print results
print(power(2, 5))
print(combination(5, 2))
def fast_power(base, exp):
# Fast power
if exp == 0:
return 1
if exp % 2 == 0:
return fast_power(base * base, exp // 2)
return base * fast_power(base, exp - 1)
print(fast_power(2, 10))Expected output
1024
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Print the results: match the terms
| Term | Meaning |
|---|---|
fast_power |
Fast power |
even |
Halve via square |
odd |
Decrease by 1 |
O(log n) |
Complexity |
2 What is fast_power's complexity?
- O(n)
- O(n^2)
- O(2^n)
- O(log n) Correct answer
Explanation: It is O(log n).
3 Even check
if exp ____ 0, exp is even.if exp % 2 == 0, exp is even.Explanation: % 2 == is right.