Question

Recursion Part

//1. Write out the output for eaching of following:

/* Consider this function.

void myMethod( int counter)

{

if(counter == 0)

return;

else

{

System.out.println(""+counter);

myMethod(--counter);

return;

}

}

This recursion is not infinite, assuming the method is passed a positive integer value. What will the output be?

b. Consider this method:

void myMethod( int counter)

{

if(counter == 0)

return;

else

{

System.out.println("hello" + counter);

myMethod(--counter);

System.out.println(""+counter);

return;

}

}

If the method is called with the value 4, what will the output be? Explain.

c.

public class Recursion {

public static void mystery1(int a, int b) {

if (a <= b) {

int m = (a + b) / 2;

System.out.print(m + " ");

mystery1(a, m-1);

mystery1(m+1, b);

}

}

public static void mystery2(int n) {

if (n > 0) {

System.out.print(n + " ");

mystery2(n-2);

mystery2(n-3);

System.out.print(n + " ");

}

}

public static void mystery3(int n) {

if (n == 0 || n == 1) return;

mystery3(n-2);

System.out.print(n + " ");

mystery3(n-1);

}

public static String mystery4(int n) {

if (n <= 0) return "";

return mystery4(n-3) + n + " " + mystery4(n-2) + n + " ";

}

public static void main(String[] args) {

int N = 5;

mystery1(0, N);

System.out.println();

mystery2(N);

System.out.println();

mystery3(N);

System.out.println();

System.out.println(mystery4(N));

}

}

Answer 1

Hi,

Hope you are doing fine. I have executed the above three codes to fetch their execution and output. Although an explanation is asked for only question b), if have provided the explanation for all the 3 codes. The explanation for code 3 is quite difficult as it undergoes a lot of recursive calls and returns, I have still tries my best to give you an idea of how the recursive calls occur.

Question a)

The program prints the list of numbers starting from the entered value (N) to 1, decreasing order with every number in new line as the output. However, if the integer passed is 0 then it does not print anything.

Explanation:

When myMethod() is called with 10 then:

· If condition on line 6 is checked, it is false

· Line 10 is executed, 10 (passed parameter) is printed and recursion happen at line 11 where myMethod is called using 9 as parameter.

· The same process is repeated till the passed parameter during recursion is 0. Once the counter becomes 0, the recursion ends.

Executable code:

Output: (if the passed integer is not 0)

Output: (if the passed integer is 0)

(blank output)

Program b)

The program gives an output where the first 4 lines contain hello appended to the value passed and the value is decremented. From the fifth line we print only the numbers from 0 increasing upto the number that was passed.

Explanation:

1. We call myMethod() using the parameter 4.

2. Line 6 is checked, the condition is false so the else part is executed.

3. Now, Line 10 is executed i.e Hello appended by 4 (passed parameter is printed

4. Now, recursion begins by passing 3 (decreasing passed parameter by 1) as the new parameter.

5. Steps 1-4 are repeated until the passed parameter becomes 0

6. Once the counter is 0 then Line 12 for each recursion call is executed and thus the numbers will be printed from 0 to 3

For input value: 4

Executable code:

Output:

Program c)

Explanation: If we understand the logic of one mystery() method, then all the other methods can be similarly understood.

1. In line 34, we call mystery(0,N) where N=5.

2. Condition on Line 4 is checked. It is true and thus m=(0+5)/2 which gives m=2

3. We print the value of m and the recursion for line 7 begin by passing parameters (0,1)

4. Now the above three steps are repeated again and 0 is printed beside 2. Method is further called using (0,-1) as parameters.

5. The condition fails in the next recursive call and line 8 for all recursive calls execute following the same process.

6. The recursion of line 8 prints 1 4 3 5 after four calls and the control is shifted back to the main() as the function call that started at line 34 is completed.

7. Further lines of code are executed and the final output can be seen in the image.

Executable code:

Output: