We 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.

2ⁿ

calculation

pattern

2⁰

2¹

2²

2³

2⁴

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) = 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