We have a function powersOfTwo() that will calculate 2**n using recursion. To ge
ID: 3934468 • Letter: W
Question
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!
Explanation / Answer
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)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.