Print the results

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.

Exercise 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)).

Show example 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))

Test yourself

Print the results: match the terms

fast_power

Fast power
even

Halve via square
odd

Decrease by 1
O(log n)

Complexity
What is fast_power's complexity?
- O(n)
- O(n^2)
- O(2^n)
- O(log n)
Show answer

O(log n) — It is O(log n).

Even check

if exp ____ 0, exp is even.

Show answer

if exp % 2 == 0, exp is even.

Next lesson: Binary search idea

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies