## frogboy77 73 Posting Pro in Training

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);
}

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

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 73

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

## frogboy77 73

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

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.

``````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!