Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
[Tutorial] recursion
Author Message
Andy

Posted: Tue Nov 25, 2003 9:11 pm   Post subject: [Tutorial] recursion

ok, this doesnt necessarily have to go under turing, but since everybody who does c++ here already noe it, i'll just write this for the noobs of the site.

what is recursion? recursion is a function or procedure that reruns itself while it is running. this may sound confusing, but you'll understand how it works and why ppl use it

recursion is especially usefull for AI programming, although it may be unefficent, you can simply use the alpha-beta method to enhance it. the alpha-beta method simply stops a tree when it realizes that the tree cannot be te result one

the best example for recursion would be an factorial program, every body knows what factorials are rite? 0!=1 1!=1 2!=2 3!=6 4!=24 5!=120 6!=720 7!=5040 8!=40320. n!=n*(n-1)*(n-2)*(n-3)*...*1 where n is an nonegative integer. i noe i noe, you're probably thinking of using a for loop to solve this problem, but why ruin the fun?

a recursive process can be an procedure or a function. if you want to return only one result, use function, if multiple use procedure. for factorial, we only want the answer so a function will be used

 code: function multiply_by_a_factorial(int num, product):int     if num=0 then         result product     end if     result multiply_by_a_factorial(num-1, product*num) end if end multiply_by_a_factorial

when accessing the function simply type

 code: multiply_by_a_factorial(6,1)

that would give an answer of 720

as you can see, within our factorial function, it calls it self again, but gives the new value to be multiplied one less than the original. and that the first thing it checks is whether if it should stop the recursive process.

you could practice your recursion skills by making your own drawfill procedure. hint, check all 8 sides around the current dot and if one of the dot is not the color you want, run the precedure again from that location.

use this for the checking
 code: for i:-1..1     for j:-1..1         if whatdotcolor(currentx+i,currenty+j) not= desiredcolor             return mydrawfill(currentx+i,currenty+j,desiredcolor)         end if     end for end for

make sure to set the boundry of the screen so you dont keep on filling nothing!

well thats the best way i could explain recursion, feel free to add what ever you can here.

for a more advanced example of recursion, look at my FP for last yr, othello. both the normal and advanced AI uses recursion to predict what the best move is. (the ultimate AI makes random moves, it was meant to be a joke)

here is the link http://www.compsci.ca/v2/viewtopic.php?t=1315&postdays=0&postorder=asc&start=0

ps. mods, i need bits! bad!

Tony

Posted: Tue Nov 25, 2003 11:30 pm   Post subject: (No subject)

wow dodge... didn't know you had that in you... +Bits

Just to add - you can search through mazes with recursion, since you can easily get it to act like a Draw.Fill. Just "fill" the pathways untill you ether find the exit or return back to the start.

If anyone interested in maze solving - ask Martin (aka Darkness)
Tony's programming blog. DWITE - a programming contest.
Andy

Posted: Wed Nov 26, 2003 12:53 pm   Post subject: (No subject)

yea, but why use recursion for that when you can use whatdotcolor? well thats next
SilverSprite

Posted: Sat Nov 29, 2003 4:19 pm   Post subject: (No subject)

tony wrote:

If anyone interested in maze solving - ask Martin (aka Darkness)

why darkness? you should be asking bugz..
Tony

Posted: Sat Nov 29, 2003 5:41 pm   Post subject: (No subject)

well yeah... true... martin and jack worked on that maze program together, but since I chat with martin soo much more, go figure.
Tony's programming blog. DWITE - a programming contest.
SilverSprite

Posted: Sat Nov 29, 2003 5:41 pm   Post subject: (No subject)

jack did the maze part
Tony

Posted: Sat Nov 29, 2003 5:44 pm   Post subject: (No subject)

well sorry SilverSprite, I dont go to Massey here, let me correct myself.

If anyone interested in maze solving - ask Jack (aka Bugz)
Tony's programming blog. DWITE - a programming contest.
Andy

Posted: Sun Nov 30, 2003 8:33 pm   Post subject: (No subject)

HEY! no spamming in my tutorial! somebody move the junk... just keep tony's first and last post

SilverSprite

Posted: Sun Nov 30, 2003 8:35 pm   Post subject: (No subject)

dodge is a loser
lets guess what dodge says next.. ."die SS!"
Andy

Posted: Sun Nov 30, 2003 9:00 pm   Post subject: (No subject)

die ss

on wed in sc
AsianSensation

Posted: Sun Nov 30, 2003 9:25 pm   Post subject: (No subject)

Weds SC? I thought it was Thur SC?
Andy

Posted: Sun Nov 30, 2003 9:44 pm   Post subject: (No subject)

yea but ss doesnt show up on thurs, and on wed we're all gonna play nywayz
Andy

Posted: Mon Dec 01, 2003 6:47 pm   Post subject: (No subject)

ok now that i'm done my whatdotcolor tutorial, ppl dont read this, read the other one... recursion is useless with whatdotcolor
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 13 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: