Basic C++ Recursion program questions

Question

//This program finds the GCD of two numbers using a recursive function call via the
//Euclidean algorithm

#include <iostream>
#include <cmath>
using namespace std;

int GCD (int A, int B);

int main()
{
    int A = 45, B = 55;

    cout << "The GCD is " << GCD(A,B) << endl;
    //test
    return 0;
}

int GCD (int A, int B)
{
    A = abs(A);
    B = abs(B);


    if (A > B)
    {
        A = A - B;
        return GCD (A, B); //Recursive function call - works fine
        //GCD (A, B);  -- This function call seems to return an incorrect value

    else if (A < B)
    { 
        B = B - A;
        return GCD (A, B);//Recursive function call
        //GCD (A, B); -- This function call seems to return an incorrect value
    }

    else if (A = B)
    {
        return A;
    }
}

Here's my question: I've noticed that if I dont use the "return" keyword in my recursive function call, the program returns an incorrect value, but if I step through the function, the values in local correctly update. I know that functions (unless they are of the type void) must return a value. Perhaps this rule applies in recursive function calls as well?

Could someone please elaborate/help me understand?

Answer 1

With the return GCD(A,B); version, the result of call GCD(A,B) is returned to the parent. If you skip the return statement, then the result returned is lost and not passed to the calling invocation of GCD().

That is, in "C", you must use the return statement for a function to return a value.

Answer 2

I know that functions (unless they are of the type void) must return a value. Perhaps this rule applies in recursive function calls as well?

Yes, it does. If you don't use the return statement, the return value of a function is undefined.

Answer 3

If you do not return a value then it's undefined what value is returned. So if none of your if/else if matches you return an unpredictable value (depends on compiler/compiler flags/time of the day you run your program/...). So the calling method will calculate wrong results.

This is true for recursive and non-recursive methods and functions.

Answer 4

Perhaps this rule applies in recursive function calls as well?

Why should different rules apply? Recursive functions work exactly like normal functions.

By the way, your program contains an error:

else if (A = B)
{
    return A;
}

This is not a comparison, it’s an assignment – and furthermore the test is unnecessary, since all other conditions (A < B and A > B) have already been tested.

Answer 5

"perhaps this rule applies in a recursive call as well"

Sure, recursion is not a special case. Your function needs to return something and in this case it's the return value of the recursive call that needs to be returned.

There's another silent error: You wrote (A=B) insteadl of (A==B)

Answer 6

The way to get your head around this is as nested function calls. The outer GCD calls an inner GCD, which in turn calls an inner GCD. When you get to the innermost call (the one where A == B), you will return A, and that return will propagate through all you return values until it reaches the outermost GCD, which will return the correct value. Without the returns, the result of the innermost call will never make it to the outside world.

Try writing down what the function does with simple values, and you'll see this nesting behaviour.

Edit: if you've been using Lisp, you might be confused, because Lisp automatically returns the last line of a function.