Recursive power
- Algorithms course
- Beginner
- Lesson 50/80
- 4 min
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.
Practice 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)).
Starter code
def power(base, exp):
# Compute power
if exp == 0:
return 1
return base * power(base, exp - 1)
def combination(n, k):
# Compute combinationSample 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))Expected output
10
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is combination's base case?
- k = 1
- n = 0
- k = 0 or k = n Correct answer
- n = k = 0
Explanation: If k=0 or k=n, return 1.
2 Two calls
Question
C(n,k) = C(n-1, k-1) + ____
Answer
C(n,k) = C(n-1, k-1) + C(n-1, k)Explanation: C(n-1, k) is right.
3 Recursive power: match the terms
| Term | Meaning |
|---|---|
combination |
Combination |
Pascal |
Two calls |
k=0 |
Base |
C(n-1,k-1) |
Choose |