Topic 10: Recursion Study Guide Understand base case and how to reduce problems
ID: 3729147 • Letter: T
Question
Topic 10: Recursion Study Guide Understand base case and how to reduce problems to smaller subproblems Being able to read and write recursion code . . 1. Read the following code. What is fun0 actually doing? public int fun(int a, int b) if (b 0) return e; if(b % 2 == 0) return fun (ata, b/2); return fun (ata, b/2) a; 2. Implement the following power) method, where x is the base and n is the exponent. private static long power(int x, int n) long y - e; // base case return 1; return x; else if( /I recursion and local work else f y power(--(3) return y return x * y; Stretch question: why do we return y when n%2-0 and return x * y at the end of the methodExplanation / Answer
1)
fun() is computing the product of a and b. That is a *b.
If a=3 and b=2 , the function will ouput 6.
2)
private static long power(int x,int n)
{
long y=0;
if(n==0)
return 1;
else if(n==1)
return x;
else
{
y=power(x,n/2);
y=y*y;
if(n%2==0)
return y;
}
return x*y;
}
Here
1) n==0
2) n==1
3) x
4) n/2