beginner problem with fuction return

[frogboy77]

trying to write a fuction to work out the GCD of two numbers
seems to run ok but the return is incorrect
any help much appreciated

#include <iostream>
#include <cmath>

using namespace std;

int g_c_d(int a,int b);

int main()
{
cout<<g_c_d(2871,4060);/*test example*/

cout<<endl;
system("pause");/*been advised not to use this but at my level well hey!*/
return 0;
}

int g_c_d(int a,int b)
{
int c;
c=abs(b-a);
cout<<a<<" "<<b<<" "<<c<<endl;/*put this in to check it was going ok*/
if(c==0){return a;}
if(b>a){b=a;}
a=c;
g_c_d(a,b);
}

returns 4249024 instead of 29

sorry this may be double post just new to this
didnt know wether it should be code snippet or discussion thread

[dusktreader]

You have a few problems:
1. This is a recusion problem, but you are not recursing correctly:

int g_c_d(int a,int b)
{
    int c;
    c=abs(b-a);
    cout<<a<<" "<<b<<" "<<c<<endl;/*put this in to check it was going ok*/
    if(c==0){return a;}
    if(b>a){b=a;}
    a=c;
    g_c_d(a,b); [B]// This value should be returned[/B]
}

2. You aren't implementing the algorithm correctly. This algorithm is looking for multiplicative factors, so you will need to do some division (by modulus):

This is the recursive Euclidean Algorithm for GCD in pseudocode:

function gcd( a, b ):
    if b = 0
       return a
    else
       return gcd( b, a mod b )

Try to implement this, and let us know how it goes.

[frogboy77]

ok not got the hang of recursion and will try this but
why is the return value as it is?

[frogboy77]

ok small change to this

int g_c_d(int a,int b)
{
int c;
c=abs(b-a);
cout<<a<<" "<<b<<" "<<c<<endl;/*put this in to check it was going ok*/
if(b>a){b=a;}
a=c;
if(c!=0){return g_c_d(a,b);}

return b;
}

seems to give correct answer but just looks wrong to me

[dusktreader]

You are returning the result of the function call. This is basically forwarding the result of the function at a lower level to the call at a higher level.

Think about this simple recursive function:

function sum_dum( number ):
    if number == 0:  # This is the base case
        return 0
    else:
        return 1 + sum_dum( number -1 )  # This is the recursive call

Now, let's see how it works:

main program scope:
-------------------
  number = 4
  print sum_dum( number ) -> passes off to number to first recursion level

---------------------
first recursion level
---------------------
  number == 4
  number != 0
  return 1 + result of second recursion level on number -1

----------------------
second recursion level
----------------------
  number == 3
  number != 0
  return 1 + result of third recursion level on number -1

---------------------
third recursion level
---------------------
  number == 2
  number != 0
  return 1 + result of fourth recursion level on number -1

----------------------
fourth recursion level
----------------------
  number == 1
  number != 0
  return 1 + result of fifth recursion level on number -1

---------------------
fifth recursion level
---------------------
  number == 0  <----- Aha!  The base case
  return 0

----------------------
fourth recursion level
----------------------
  return 1 + 0  <- result of fifth level

---------------------
third recursion level
---------------------
  return 1 + 1  <- result of fourth level

---------------------
second recursion level
---------------------
  return 1 + 2  <- result of third level

---------------------
first recursion level
---------------------
  return 1 + 3  <- result of second level

----
main
----
  got 4 back from sum_dum!

Now, obviously, this is not useful at all. However, it shows how recursion works. The keys to recursion are:

1. Do a little bit of work at this level
2. Send the rest of the data down to the next level
3. Define a "base case" level to determine when the work is done
4. In the base case, return a simple value
5. In the non-base cases return the result of this level's work and the result of the next level down

I know recursion is somewhat confusing for beginners. However, if you can master this design paradigm, you will be amazed at some of the complicated problems that can be solved very simply and elegantly.

Good luck!

[dusktreader]

seems to give correct answer but just looks wrong to me

It is wrong. GCD algorithm is looking for multiplicative factors. So, subtraction is not the right method here. If you are getting correct results, I think it is coincidental. Read my first response. You need to use modulus.

[frogboy77]

ok have tried your code and it works beautifully(will use it from now)
but try my amended code against yours and see if the answer is correct
it takes more calculations but they are just subtractions
dont know if subtractions are quicker or slower than modulus operations(noob)
would be pleased to know if it was luck that gave correct answer or not.
p.s came across the subtraction thing on wikipedia