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 - 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 monoonly calls itself once tell you about how it executes?

Q3: Try to guess the result of calling binary(2,"");. What does the fact that binarycalls 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 Q2and Q3.

Q4: What is the actual output of mono(2,""); and binary(2,"");? Explain the output in terms of ap- pending the characters 'a' and 'b' 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

If anything else,then please ask.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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