CODEWITHSUNDEEP
cfunctionrecursion
Saideep Pavuluri
Saideep Pavuluri

Reputation: 102

While using recursive function calls when to use 'return'?

I am confused when to use 'return' while using recursive function calls.

I am trying to find the "GCD (Greatest common divisor)" of two numbers. What I actually thought would work is: 

  include <stdio.h>
  int gcd (int a, int b);

  int main ()
  {
   int a, b;
   printf ("Enter two numbers \n");
   scanf ("%d %d", &a, &b);
   printf ("GCD for numbers %d and %d is %d\n", a, b, gcd(a,b));
   return (0);
   }

   int gcd (int a, int b)
   {
    while (a!=b)
     {
      if (a > b)
       gcd(a-b,b);
      else if (b > a)
       gcd(a,b-a);
     }
    return (a);
   }

But the above code continuously accepts numbers from terminal and fails to run the code.

However, when I replace the function definition as follows the code works as expected returning the right values. 

   int gcd (int a, int b)
   {
    while (a!=b)
     {
      if (a > b)
       return gcd(a-b,b);
      else if (b > a)
       return gcd(a,b-a);
     }
    return (a);
   }

As you see the only change is addition of 'return' before the recursive function call. Why is return required there considering in both the cases I am calling the gcd(arg1, arg2) function?

Upvotes: 0

Views: 698

Answers (2)

Karl Knechtel
Karl Knechtel

Reputation: 61519

Why is return required there considering in both the cases I am calling the gcd(arg1, arg2) function?

For the same reason that it is required any other time you call a function and wish to return the value that was returned by that function call; because calling it only calls it, and does nothing else with the resulting value.

I am confused when to use 'return' while using recursive function calls.

Use return for a recursive call, whenever you would use return for any other function call - i.e.: when, and because, that call returns the value you wish to return this time around.

Imagine that we have

#include "magic.h" /* defines gcd2(), which computes GCD in some mysterious way */

And then instead of making recursive calls, we delegate some of the work to that:

/* Of course this solution also works, but is not interesting
int gcd(int a, int b)
{
    return gcd2(a, b);
} */

/* So, let's do something that actually shows off the recurrence relation */
int gcd(int a, int b)
{
    if (a > b)
        return gcd2(a-b, b);
    else if (b > a)
        return gcd2(a, b-a);
    else
        return a;
}

(I also removed the while loop, because it is not relevant to the algorithm; of course, a return is reached in every circumstance, and this breaks the loop.)

I assume I don't need to go over the mathematical theory; and also I assume it is clear why return is needed for the gcd2 results.

But it doesn't actually matter how the work is delegated; if gcd is a function that correctly computes GCDs, and gcd2 is also such, then a call to gcd2 may be replaced by a call to gcd. This is the secret - calling a function recursively is not actually different from calling one normally. It's just that considering the possibility, requires a clearer understanding of how calling a function works and what it actually does.

Of course, it is also possible to make good use of the original while loop - by subtracting out as much as possible before doing the recursion. That might look like:

int gcd(int a, int b)
{
    if (a > b)
        while (a > b)
            a -= b; /* prepare a value for the recursion. */
        return gcd(a, b); /* and then recurse with that value. */
    else if (b > a)
        while (b > a)
            b -= a; /* similarly. */
        return gcd(a, b);
    else /* a == b */
        return a;        
}

But then we might as well go all the way and convert to an iterative approach:

int gcd(int a, int b)
{
    while (a != b)
        /* whichever is greater, adjust it downward, leaving an (a, b)
           pair that has the same GCD. Eventually we reach an equal pair,
           for which the result is known. */
        if (a > b)
            a -= b;
        else
            b -= a;
    return a; /* since the loop exited, they are equal now. */
}

(And we also could do modulo arithmetic to accomplish multiple subtractions at once; this is left as an exercise.)

Upvotes: 3

Peter G.
Peter G.

Reputation: 15124

The first gcd function "tries" to compute the gcd but in the end always returns a unchanged.

The second gcd function computes the gcd recursively and each invocation returns a gcd.

Upvotes: 0

Related Questions