Question

What is the output of the following recursive function? \[ \texttt{int\ func1(int\ num1,\ int\ num2)} \]

return (num2 == 0) ? num1 : func1(num2, num1 % num2);
  

• A. Factorial of num1
• B. Fibonacci numbers from num1 to num2
• C. GCD of num1 and num2
• D. LCM of num1 and num2

Hint:

Euclid's Algorithm: \[ GCD(a,b)=GCD(b,a\bmod b) \] until \(b=0\).

Answer 1

The Correct Option is C

Concept: The function repeatedly replaces: \[ (num1,num2) \] with \[ (num2,num1 \bmod num2) \] until \[ num2=0. \] This is exactly the Euclidean Algorithm for computing the Greatest Common Divisor (GCD).

Step 1: Observe the recursive call.
The recursive statement is: \[ func1(num2,num1%num2) \] which is the standard Euclidean reduction step.

Step 2: Observe the stopping condition.
The recursion stops when: \[ num2=0 \] and returns: \[ num1. \] At that stage \(num1\) contains the GCD.

Step 3: Verify using an example.
Let: \[ num1=12,\quad num2=8 \] Then: \[ func1(12,8) \] \[ \rightarrow func1(8,4) \] \[ \rightarrow func1(4,0) \] \[ \rightarrow 4 \] Hence the result is the GCD.

Step 4: Write the answer.
Therefore the function computes \[ \boxed{\text{GCD of num1 and num2}} \] Hence option (C) is correct.