1) As we can see from the text, this image purports to be an example of recursio
ID: 3847894 • Letter: 1
Question
1)
As we can see from the text, this image purports to be an example of recursion. Justify this by (informally) describing an algorithm that would draw this image. Assume the algorithm would be implemented by a single method called drawRecursion that takes a parameter describing the region of the image that needs to be filled in. The answer must include a description of the base case, the work done in each call, and the recursive call (e.g. parameters).
2)
[KB] The sum of the first n positive integers is:
and can easily be computed using a for-loop:
public int sumToN(int n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
It is also possible to recursively compute the sum by recognizing that sum(n) = n + sum(n - 1). Write a recursive version of sumToN(...).
3)
[SB] Consider the following recursive method:
public static int run1(int n){
if(n < 1)
return 2;
else
return 2 + run1(n-3);
}
What is run1(6)? How many times does the method call itself?
4)
[SB] What does the following recursive function do? Give a high-level description, don't just reword the code into English (e.g., "if the number is less than or equal to 1, it returns 1").
// assume number is always greater than 1
public static int foo(long number){
if(number <= 1)
return 1;
else
return n*foo(n-1);
}
RECURSION RECURSION RECURSIO RECURSION RECURSION RECURSION Here we go again RECURSION Here we go again RECURSION Here we go again RECURSION Here we go again RECURSION Here we go againExplanation / Answer
1) You can simply implement a function that takes in the length and breadth of the rectangle i.e. x and y. If the length or the breadth any thing goes to zero, just simply return.
public static void draw(double x, double y) {
if (x == 0 || y ==0 ) return;
draw(x - size/2, y - size/2);
}
2) It is very easy to implement, just for the base case that is if number is 1, return 1 otherwise iterate over all the number from n = 1. Here is the code:
public static int sumToN(int n) {
if(n==1) return 1;
return n+sumToN(n-1);
}
3) run1(6) will return 6, how? If the number is less than 1, then a answer is 2 otherwise, it subtracts 3 from it. So, we have 6 not less than one so, there is one recursive call for 6-3 i.e. 3. Again we have 3 which is also not less than 1, again we have a recursive call for 3-3 i.e. 0. Now, 0 is less than 1. No more recursive calls. Hence, the method calls itself 2 times.
4) A high-level description would be, it returns the factorial of the number provided. However, there is lot of errors in the function itself. The function returns long*int --> which is an error. Here is a debugged version of the function. The gist of the function was still clear.
public static long foo(long n){
if(n <= 1)
return 1;
else
return n*foo(n-1);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.