Implement the following recursive algorithm in your Java IDE to test how the number of recursive calls increase as n grows. Choose several values of n to be able to investigate the runtime. Attach your code and table to show values of n and number of calls.

Then show how you would solve the recurrence relation to find the runtime of the function. Does your empirical investigation match your analysis based on solving the recurrence relation?

void printOnes (int n) {

if (n = 0)

System.out.println("1");

else {

for( int i = 1; i <= 2^n; i++)

printOnes(n-1) ;

}

}