Computer Science Canada

A problem with Recursions
Author:  timmytheturtle [ Mon Sep 27, 2004 4:47 pm ]
Post subject:  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.

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."
Author:  timmytheturtle [ Mon Sep 27, 2004 5:00 pm ]
Post subject: 
anyone Question
Author:  Cervantes [ Mon Sep 27, 2004 5:06 pm ]
Post subject: 
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
Author:  timmytheturtle [ Mon Sep 27, 2004 5:20 pm ]
Post subject: 
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
Author:  Cervantes [ Mon Sep 27, 2004 6:25 pm ]
Post subject: 
...
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.
Author:  timmytheturtle [ Mon Sep 27, 2004 8:02 pm ]
Post subject: 
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
Author:  Tony [ Mon Sep 27, 2004 8:13 pm ]
Post subject: 
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 Wink
Author:  Cervantes [ Tue Sep 28, 2004 4:40 pm ]
Post subject: 
tony: how would you write a recursive function to find the GCF? mine's so lame 8)
Author:  AsianSensation [ Tue Sep 28, 2004 8:41 pm ]
Post subject: 
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
Author:  wtd [ Tue Sep 28, 2004 9:27 pm ]
Post subject: 
code:
let rec gcd a b =
   if b = 0 then a
   else gcd b (a mod b)


Smile

Sorry, just needed to see some sane code to take my mind off being sick.
Author:  apomb [ Tue Sep 28, 2004 10:26 pm ]
Post subject: 
hmmm, seems wtd is feeling under the weather, that doesnt seem very "sane" to me... Thinking

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
Author:  AsianSensation [ Tue Sep 28, 2004 10:47 pm ]
Post subject: 
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.
Author:  wtd [ Tue Sep 28, 2004 11:06 pm ]
Post subject: 
CompWiz333 wrote:
hmmm, seems wtd is feeling under the weather, that doesnt seem very "sane" to me... Thinking


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.
Author:  wtd [ Tue Sep 28, 2004 11:07 pm ]
Post subject: 
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).
Author:  wtd [ Tue Sep 28, 2004 11:31 pm ]
Post subject: 
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


Smile

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.
Author:  apomb [ Wed Sep 29, 2004 11:59 am ]
Post subject: 
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!
Author:  wtd [ Wed Sep 29, 2004 12:01 pm ]
Post subject: 
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.

code:
def term(n)
   case n
      when 1
         2
      when 2
         4
      else
         term(n - 1) ** 2 - 3 * term(n - 2)
   end
end

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy