----------------------------------- timmytheturtle Mon Sep 27, 2004 4:47 pm A problem with Recursions ----------------------------------- 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. 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 Mon Sep 27, 2004 5:00 pm ----------------------------------- anyone :?: ----------------------------------- Cervantes Mon Sep 27, 2004 5:06 pm ----------------------------------- 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. :wink: ----------------------------------- timmytheturtle Mon Sep 27, 2004 5:20 pm ----------------------------------- 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 Mon Sep 27, 2004 6:25 pm ----------------------------------- ... 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. 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 Mon Sep 27, 2004 8:02 pm ----------------------------------- 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 Mon Sep 27, 2004 8:13 pm ----------------------------------- 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 :wink: ----------------------------------- Cervantes Tue Sep 28, 2004 4:40 pm ----------------------------------- tony: how would you write a recursive function to find the GCF? mine's so lame 8) ----------------------------------- AsianSensation Tue Sep 28, 2004 8:41 pm ----------------------------------- well, there is the Euclid's Algorithm: function gcd (a, b : int) : int if b = 0 then result a else result gcd (b, a mod b) end if end gcd ----------------------------------- wtd Tue Sep 28, 2004 9:27 pm ----------------------------------- 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 Tue Sep 28, 2004 10:26 pm ----------------------------------- hmmm, seems wtd is feeling under the weather, that doesnt seem very "sane" to me... :think: 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 Tue Sep 28, 2004 10:47 pm ----------------------------------- something like this: 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 Tue Sep 28, 2004 11:06 pm ----------------------------------- hmmm, seems wtd is feeling under the weather, that doesnt seem very "sane" to me... :think: It's quite sane. It just requires thinking in a different way. let rec gcd a b = Create a recursive function "gcd" which takes two arguments, a and b. 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 Tue Sep 28, 2004 11:07 pm ----------------------------------- something like this: 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 Tue Sep 28, 2004 11:31 pm ----------------------------------- 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 :) # 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 = # 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. ----------------------------------- apomb Wed Sep 29, 2004 11:59 am ----------------------------------- i see, however, this IS in the Turing section, not O'Caml ... whatever, i understand it now, just have to input each term and use formula ... the nth thing screwed me up thanks guys, really helped! ----------------------------------- wtd Wed Sep 29, 2004 12:01 pm ----------------------------------- Sorry about that. Problem is, I don't have access to Turing, so at best I'd be guessing how to write the code, and I did want to actually include some working code. Perhaps Ruby would be a closer match for Turing, though. def term(n) case n when 1 2 when 2 4 else term(n - 1) ** 2 - 3 * term(n - 2) end end