This lab is about recursion. Recursion is a way of programming by repeatedly bre

Question

This lab is about recursion. Recursion is a way of programming by repeatedly breaking problems down into smaller problems of the same type until they are so small they are trivial to solve. This typically involves the use of methods that call themselves.

Here we will implement some functions that are fairly mathematical, not because that is the only thing recursion is useful for, but because the applications of recursion that you see in practice require a little more setup, and I just want to introduce you to the basic concept.

Remember from class that recursive methods generally have two parts %u2014 a recursive case, where the recursive method is called inside itself, and a base case, where the method is not called. In the examples I give you here, these cases are broken out by if statements, although in more complicated examples this need not be the case.

I will be asking you to both do some coding and also to answer some questions. The questions are in italics and are identified by Q1, Q2, Q3, . . .

1 Two examples

Observe the following two methods.

}

}
Q1: Identify the base and recursive cases for both mono and binary.

Q2: Try to guess the result of calling mono(2,"");. What does the fact that mono only calls itself once tell you about how it executes?

Q3: Try to guess the result of calling binary(2,"");. What does the fact that binary calls itself twice tell you about how it executes?

Type the two methods below into a test class and see what they do by calling them from main with a couple different arguments, including the ones from Q2 and Q3.

Q4: What is the actual output of mono(2,""); and binary(2,"");? Explain the output in terms of ap- pending the characters %u2019a%u2019 and %u2019b%u2019 to the end of strings and then eventually printing the strings. When does the printing happen?

Q5: What is the danger of calling binary(500,""); ? Why is this not as dangerous as calling mono(500,"");? 1 of 2

2 GCD ( Greatest Common Divisor )

The GCD of two numbers is the largest number that divides both of them without leaving a remainder.

The Euclidean algorithm is based on the principle, that the greatest common divisor of two numbers does not change, if the smaller number is subtracted from the larger number.

For example, Euclidean algorithm can be used to find the greatest common divisor of a = 1071 and b = 462

To begin, multiples of 462 are subtracted from 1071 until the remainder is less than 462. Two such multiples can be subtracted (q0 = 2), leaving a remainder of 147

1071 = 2 * 462 + 147

Then multiples of 147 are subtracted from 462 until the remainder is less than 147. Three multiples can be subtracted (q1 = 3), leaving a remainder of 21

462 = 3 * 147 + 21

Then multiples of 21 are subtracted from 147 until the remainder is less than 21. Seven multiples can be subtracted (q2 = 7), leaving no remainder

147 = 7 * 21 + 0
Since the last remainder is zero, the algorithm ends with 21 as the greatest common divisor of 1071 and 462

Iterative implementation of Division based Euclidean Algorithm is given below -

}

return a; }

Now, write a recursive function

that returns GCD of a and b.

Explanation / Answer

please rate - thanks

any questions ask

1 Two examples

Observe the following two methods.

}

}
Q1: Identify the base and recursive cases for both mono and binary.      --see methods above

Q2: Try to guess the result of calling mono(2,"");. What does the fact that mono only calls itself once tell you about how it executes?

x="",n=2 so call mono(1,"a")

x=a,n=1 so call mono(0,aa)

n=0 so output aa

return to call where n=1

return to call where n=2

Q3: Try to guess the result of calling binary(2,"");. What does the fact that binary calls itself twice tell you about how it executes?

x="", n=2 so call binary(1,a)

x=a,n=1 so call binary(0,aa)

n=0 so output aa

return to after call banary(0,aa)

x=a,n=1 so call binary(0,ab)

n=0 so output ab

return to call after binary(1,a)

x="", n=2 so call binary(2,b)

x=b,n=2 so call binary(1,ba)

x=ba, n=0 so output ba

return to last call

x=b,n=1 so call binary(0,bb)

x=bb,n=0 so output bb

return and return to main

Type the two methods below into a test class and see what they do by calling them from main with a couple different arguments, including the ones from Q2 and Q3.

Q4: What is the actual output of mono(2,"");  

aa

and binary(2,"");?

aa

ab

ba

bb

Explain the output in terms of ap- pending the characters %u2019a%u2019 and %u2019b%u2019 to the end of strings and then eventually printing the strings.

mono appends n occurances of a

binary appens n occurances of a and b in every combination

When does the printing happen?

in both cases when you reach the base case

program used

import java.util.Scanner;
public class main
{ public static void mono(int n,String x){ if(n<=0){

System.out.println(x); }else{

mono(n-1,x+"a"); }

}

public static void binary(int n, String x){ if(n<=0){

System.out.println(x); }else{

binary(n-1,x+"a");

binary(n-1,x+"b"); }

}      public static void main(String[] args)

      {mono(2,"");
        binary(2,""); }
}

actual output

Q5: What is the danger of calling binary(500,""); ?

Why is this not as dangerous as calling mono(500,"");? 1 of 2

mono will only print 500 a's

whereas binary will print all combinations of a and b 500 characters each combination

   public static int GCD(int m,int n)
   {if(m<n)
       return GCD(n,m);
   else if(m%n==0)
       return n;
   else
       return GCD(n,m%n);
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.