Function

bryan

Member
Joined
Jul 17, 2004
Messages
11
Programming Experience
Beginner
Hi, I was trying to write an alogorithm so it could find the GCF(Greatest Common Factor) of two numbers, and someone gave me a function along with some other code. but my question is how this function works, if anyone could explain it step by step what is doing that would be great.

VB.NET:
Public Function GCD(a As Integer, b As Integer) 
	If b Then 
		GCD = GCD(b, a Mod b) 
	Else 
		GCD = a 
	End If 
End Function
 

Deemoore

Member
Joined
Aug 8, 2004
Messages
6
Programming Experience
3-5
Sometimes the answer only supplies more questions

Firstly you need to understand what MOD does because the function recurses (reruns itself).

result = number1 Mod number2
GCD (a, b)

In the function becomes
GCD( b, the remainder of a/b )

This then divides (recourses) until there’s no remainder left
( the “If b Then” part keeps looking to see if remainder is 0 )

Public Function GCD(a As Integer, b As Integer)
If b Then
GCD = GCD(b, a Mod b)
Else
GCD = a
End If
End Function


Mod in this case returns the remainder after a is divided by b.

( “b” keeps moving over to the “a” spot and the remainder goes in the b spot )

Then the function reruns until
GCD(a, b) the second variable becomes zero (b)

you are returned the last remainder you had just before it reached zero.

Hope this helps.
 
Last edited:
Top Bottom