Homework SourseWe have a function powersOfTwo that will calculate 2n using
We have a function powersOfTwo() that will calculate 2**n using recursion. To get full credit for this problem, complete the table below (found after the example) and identify the base and recursive cases.
Example:
factorial()
n!
calculation
pattern
0!
1
1!
1
1 * 0!
2!
2 * 1
2 * 1!
3!
3 * 2 * 1
3 * 2!
4!
4 * 3 * 2 * 1
4 * 3!
Pattern gives us an algorithm for solving the problem:
base case: factorial(n) = 1, if n==0
recursive case: factorial(n) = n * factorial(n-1), if n > 0
Take a look at what the function powersOfTwo() computes for the different values of n, to identify the pattern . Complete the table.
2n
calculation
pattern
20
21
22
23
24
Identify base case:
Identify recursive case:
| n! | calculation | pattern |
| 0! | 1 | |
| 1! | 1 | 1 * 0! |
| 2! | 2 * 1 | 2 * 1! |
| 3! | 3 * 2 * 1 | 3 * 2! |
| 4! | 4 * 3 * 2 * 1 | 4 * 3! |
Solution
base case - powersOfTwo(n)=1 if n=0
Recursive case - powersOfTwo(n)=2*powersOfTwo(n-1) if n>0
Table -
20 - 1 - 1
21 - 2*1 - 2*powersOfTwo(0)
22 - 2*2*1 - 2*powersOfTwo(1)
23 - 2*2*2*1 - 2*powersOfTwo(2)
24 - 2*2*2*2*1 - 2*powersOfTwo(3)
