We have a function powersOfTwo() that will calculate 2**n using recursion. To ge
ID: 3931173 • 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) = 2, if n==1
Recursive Case
powersOfTwo(n) = 2* powersOfTwo(n-1), if n >
C++ code
int power(int powerRaised)
{
if (powerRaised != 1)
return (2*power(powerRaised-1));
else
return 2;
}
2n
calculation
pattern
20
1
21
2
22
2 * 2
2 * 2^1
23
2 * 2 * 2
2 * 2^2
24
2 * 2 * 2 * 2
2 * 2^3
2n
calculation
pattern
20
1
21
2
22
2 * 2
2 * 2^1
23
2 * 2 * 2
2 * 2^2
24
2 * 2 * 2 * 2
2 * 2^3
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.