Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 A problem with Recursions
Index -> Programming, Turing -> Turing Help
Goto page 1, 2  Next
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
timmytheturtle




PostPosted: 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."
Sponsor
Sponsor
Sponsor
sponsor
timmytheturtle




PostPosted: Mon Sep 27, 2004 5:00 pm   Post subject: (No subject)

anyone Question
Cervantes




PostPosted: Mon Sep 27, 2004 5:06 pm   Post subject: (No 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
timmytheturtle




PostPosted: Mon Sep 27, 2004 5:20 pm   Post subject: (No 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
Cervantes




PostPosted: Mon Sep 27, 2004 6:25 pm   Post subject: (No 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.
timmytheturtle




PostPosted: Mon Sep 27, 2004 8:02 pm   Post subject: (No 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
Tony




PostPosted: Mon Sep 27, 2004 8:13 pm   Post subject: (No 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
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
Cervantes




PostPosted: Tue Sep 28, 2004 4:40 pm   Post subject: (No subject)

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




PostPosted: Tue Sep 28, 2004 8:41 pm   Post subject: (No 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
wtd




PostPosted: Tue Sep 28, 2004 9:27 pm   Post subject: (No 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.
apomb




PostPosted: Tue Sep 28, 2004 10:26 pm   Post subject: (No 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
AsianSensation




PostPosted: Tue Sep 28, 2004 10:47 pm   Post subject: (No 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.
wtd




PostPosted: Tue Sep 28, 2004 11:06 pm   Post subject: (No 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.
wtd




PostPosted: Tue Sep 28, 2004 11:07 pm   Post subject: (No 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).
wtd




PostPosted: Tue Sep 28, 2004 11:31 pm   Post subject: (No 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.
Display posts from previous:   
   Index -> Programming, Turing -> Turing Help
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 2  [ 17 Posts ]
Goto page 1, 2  Next
Jump to:   


Style:  
Search: