A problem with Recursions

[timmytheturtle]

Can anyone help with finding the GCF (greatest common factor) using recursions. I'm new to recursions (just started today), and I'm having troubles, anyhelp would be greatly appreicated.

code:

function GCF (intOne : int, intTwo : int) : int     if intOne = intTwo then         result intOne             elsif intOne > intTwo then             result intOne+GCF (intOne, intTwo - intTwo)     end if     end GCF put GCF (55,88)

Edit: When I run it i got this error: "Function failed to give a result."

[timmytheturtle]

anyone

[Cervantes]

Well, the reason its not returning a result is because, using the nubers 55 and 88, 55 is not greater than 88, nor is it equal to 88, so it does not enter either of those if statements where the precious result command is.

try reversing the numbers. 88 and 55. Now you'll get a stack overflow.

[timmytheturtle]

Ok, I guess you have no idea how to fix it so I will just have to skip that question, till tommorow and I'll try and get some help

[Cervantes]

...
You're giving up because you assumed that I (one of thousands registered on this site) don't know how to do the problem? Work at it!

You were right when you made your assumption, but after working at it for a while I figured out how to do it. And I've never used recursions either, so if I can do it you can do it.

code:

var counter := -1 function GCF (i1, i2 : int) : int     if counter = -1 then         counter := min (i1, i2)     end if     if i1 mod counter = 0 and i2 mod counter = 0 then         result counter     else         counter -= 1         result GCF (i1, i2)     end if end GCF put GCF (50, 25)

not the greatest recursion, I'm sure. Works to the best of my knowledge.

[timmytheturtle]

thank you! and sorry for assuming you didnt now what to do. My teacher always tells us that if we are stuck on one question at home for so long move on to the next question and get help the next day

[Tony]

timmytheturtle wrote:

if we are stuck on one question at home for so long move on to the next question and get help the next day

clearly your teacher has never heard of compsci.ca

[Cervantes]

tony: how would you write a recursive function to find the GCF? mine's so lame 8)

[AsianSensation]

well, there is the Euclid's Algorithm:

code:

function gcd (a, b : int) : int     if b = 0 then         result a     else         result gcd (b, a mod b)     end if end gcd

[wtd]

code:

let rec gcd a b =    if b = 0 then a    else gcd b (a mod b)

Sorry, just needed to see some sane code to take my mind off being sick.

[apomb]

hmmm, seems wtd is feeling under the weather, that doesnt seem very "sane" to me...

any who ... i have a test on recursion formulas on friday and i didnt want to start a new "recursion" thread, so, heres my question, if you are given the first two terms in a sequence and the formula, how exactly would you go about finding the next four terms

first two terms are : t1=2 t2=4

tn=(tn-1)^2-3tn-2

[AsianSensation]

something like this:

code:

fcn recurse (a, b : int) : int     put b     result recurse (b, a * a - 3 * b) end recurse put recurse (2, 4)

though you get the integer overflow error pretty quick.

There is a tutorial in our tutorial section on recursion, check it out.

[wtd]

CompWiz333 wrote:

hmmm, seems wtd is feeling under the weather, that doesnt seem very "sane" to me...

It's quite sane. It just requires thinking in a different way.

code:

let rec gcd a b =

Create a recursive function "gcd" which takes two arguments, a and b.

code:

if b = 0 then a else gcd b (a mod b)

This is just your basic conditional. If b equals zero, then return a. Otherwise return the result of calling the function with b and a modulus b.

O'Caml can look odd since it eschews parentheses and commas in function definitions and calls, but you learn to love it.

[wtd]

AsianSensation wrote:

something like this:

code:

fcn recurse (a, b : int) : int     put b     result recurse (b, a * a - 3 * b) end recurse put recurse (2, 4)

though you get the integer overflow error pretty quick.

The problem is that you don't provide any end condition for the recursion. No matter what happens, the function will continue recursing forever (or until you kill your computer).

[wtd]

CompWiz333 wrote:

any who ... i have a test on recursion formulas on friday and i didnt want to start a new "recursion" thread, so, heres my question, if you are given the first two terms in a sequence and the formula, how exactly would you go about finding the next four terms

first two terms are : t1=2 t2=4

tn=(tn-1)^2-3tn-2

code:

# let rec term = function    1 -> 2    | 2 -> 4    | n -> int_of_float (float_of_int (term (n - 1)) ** 2.) - 3 * (term (n - 2));; val term : int -> int = <fun> # term 1;; - : int = 2 # term 2;; - : int = 4 # term 3;; - : int = 10 # term 4;; - : int = 88 # term 5;; - : int = 7714 # term 6;; - : int = 59505532

The key, as always with recursion, is to use what you do know to provide an escape for your recursion. In this case you know that when 1 is input you get 2 as the answer, and that when 2 is input you get 4 as the answer.

In this case especially, you need to use all of the available information. If you tried to just rely on the fact that t(2) = 4, then t(3) would recurse infinitely, since t(n - 2) would be t(1), for which there'd be no known value.