Please give me BOX TRACE of this program. // This program demonstrates a recursi
ID: 3876464 • Letter: P
Question
Please give me BOX TRACE of this program.
// This program demonstrates a recursive function to calculate
// the greatest common divisor (gcd) of two numbers.
#include <iostream>
using namespace std;
// Function prototype
int gcd(int, int);
int main()
{
int num1, num2;
// Get two numbers.
cout << "Enter two integers: ";
cin >> num1 >> num2;
// Display the GCD of the numbers.
cout << "The greatest common divisor of " << num1;
cout << " and " << num2 << " is ";
cout << gcd(num1, num2) << endl;
return 0;
}
//**********************************************************
// Definition of gcd. This function uses recursion to *
// calculate the greatest common divisor of two integers, *
// passed into the parameters x and y. *
//**********************************************************
int gcd(int x, int y)
{
if (x % y == 0)
return y; // Base case
else
return gcd(y, x % y); // Recursive case
}
Explanation / Answer
Since no input values were mentioned to be considered for building the BLOCK TRACE, I presume x and y to be 6 and 10. Their gcd is 2.
The BOX TRACE for the function gcd(6, 10) is:
FX represents Frame X.
F1 : gcd(6, 10)
What happened? since x < y, the first call interchanges the values.
F2 : gcd(10, 6)
F3: gcd(6, 4)
F4: gcd(4, 2)
What happened is that the call to gcd(4, 2) didn't make any more calls for the gcd function but rather returned. The returned value is passed up in the stack of frames.
The order of evaluation was as follows:
main function => F1 => F2 => F3 => F4 => F3 => F2 => F1 => main functoin
if (6 % 10 == 0) False else return gcd(10, 6 % 10) return 2