Recursive power

Add a recursive power(base, exp) function.

Add combination

Now we add combination(n, k). It computes how many ways k items can be chosen from n items.

Pascal's method: C(n,k) = C(n-1,k-1) + C(n-1,k). Base case: if k=0 or k=n, return 1.

Pascal's method

C(n,k) = C(n-1,k-1) + C(n-1,k). This is the sum of choosing or not choosing one element. Each case is a recursive call.

This rule enables computing combination recursively. Two calls are made and results are summed.

Exercise Combination

Write combination(n, k). If k=0 or k=n return 1, else combination(n-1,k-1) + combination(n-1,k). Print 10 with print(combination(5, 2)).

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)
print(combination(5, 2))

Test yourself

What is combination's base case?
- k = 1
- n = 0
- k = 0 or k = n
- n = k = 0
Show answer

k = 0 or k = n — If k=0 or k=n, return 1.

Two calls

C(n,k) = C(n-1, k-1) + ____

Show answer

C(n,k) = C(n-1, k-1) + C(n-1, k)

Recursive power: match the terms

combination

Combination
Pascal

Two calls
k=0

Base
C(n-1,k-1)

Choose

Next lesson: Combination

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies