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

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

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

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 again