Java

TOPIC 33 – RECURSION

LESSON WORK

QUESTION 1
What are the following recursive functions doing? Propose a better name for the function.

//A)

public static void fun(int x)

{

if(x <= 0)

{

return;

}

else

{

System.out.print("*");

fun(x-1);

}

}

//B

public static int funner(int a, int b)

{

if (b == 0)

{

return a;

}

else if (b < 0)

{

return funner(a+1, b+1);

}

else

{

return funner(a-1, b-1);

}

}

//C)

public static int funnest(int a, int b)

{

if (b < 0)

{

return funnest(-a, -b);

}

else if (b == 0)

{

return 0;

}

else if (b == 1)

{

return a;

}

else

{

return a + funnest(a, b-1);

}

}

QUESTION 2
You will implement Euclid's algorithm. It is a famous algorithm for finding the greatest common divisor between two numbers.

Here is Euclid's algorithm which has a recursive definition:

gcd(a,b) = a, if b is zero

= gcd (b,a) if a < b

= gcd (b, a mod b), otherwise

Note: In Java, mod is represented by the % symbol.

a) You are to create the function gcd(int a, int b).

b) Test out your function using different values. For example,

gcd(15, 25) should give the answer 5

and

gcd(102, 68) should give the answer 34.

c) What is the GCD of 2196 & 7438?