Follow us on Twitter!
One mans freedom fighter, another's terrorist.
Sunday, April 20, 2014
Navigation
Home
HellBoundHackers Main:
HellBoundHackers Find:
HellBoundHackers Information:
Learn
Communicate
Submit
Shop
Challenges
HellBoundHackers Exploit:
HellBoundHackers Programming:
HellBoundHackers Think:
HellBoundHackers Track:
HellBoundHackers Patch:
HellBoundHackers Other:
HellBoundHackers Need Help?
Other
Members Online
Total Online: 20
Guests Online: 19
Members Online: 1

Registered Members: 82843
Newest Member: hx47
Latest Articles

Scheme Programming 2

Arrow Image Walkthrough of more advanced functions of Scheme



Okay, the primary goal in this article will be recursion and iteration with Scheme, and this article assumes that you have either read my scheme programming 1 article or that you have some background knowledge. Also, I forgot to mention in my last article that to put comments in Scheme, you lead your comment with a semicolon (;).

(note: ! means factorial, if you donít know what that is, google it)

RECURSION:
So Iíll start with a simple recursive procedure to find factorials.
In recursive procedures, you first need to find two things:
1.) Base Case (simplest form of the problem). For example: 0!=1
2.) Recurrence Relation. Example: n!= n*(n-1)!

i apologize for the poor tabbing:

(define (fact n)
(if (= n 0) ;this is our base case
1 ;if the base case is true, the procedure will return a one
(* (fact (- n 1)) n) ;else the procedure will call itself up with n-1
)
)
So, (fact 3) will return 6. Letís walk through it now. The key difference between iteration and recursion is that recursion needs to keep all of its calls in memory because it needs to come back to perform a calculation. So letís look at this one in depth:

When you start, you call up (fact 3), which will result in 3*(fact 2), and (fact 2) is 2*(fact 1), and (fact 1) is 1*(fact 0), so once it reaches the 0, it has reached the base case which the procedure has a value for. So we end up with 1*1*2*3=6.

Activation records (stack tower):
-(fact 0)
-(fact 1)
-(fact 2)
-(fact 3)
-scheme
-op system


ITERATION:
In iterative procedures, you need to keep track of three things:
1. Starting state
2. Terminating Criteria
3. Progress
To keep things simple, Iím going to use the example of factorials again:

(define (factIter n progress partial) ;note that partial is used to keep track of the answer so far
(if (= progress n) ;terminating criteria
partial ;if the procedure is done, it will return the current answer
(factIter n (+ progress 1) (* partial (+ progress 1) ) ) ;hereís your recursive call
)
)

While there is a recursive call in the iterative solution, there is a difference. The difference is that the iterative method does not require the interpreter to keep all the method calls in memory since it doesnít have to come back to do any calculations. Another name for the iterative procedure is Ďtail-recursiveí because the recursive call is the very last thing that is done in the procedure. (recall that in the recursive method the last thing done was the multiplication procedure, not the recursive call)

Since the interpreter doesnít need to keep track of each method call, the new call can just overwrite the old one in the stack tower, so it will look like this:

-(fact 3) each call to factiter will just overwrite this one with the new call
-scheme
-op system


Iterative methods will probably run faster since the stack takes up less space and the computer doesnít have to trace down the stack, but recursive procedures are still valuable. Some problems are just naturally solved recursively such as tree methods and Fibonacci sequences.

Comments

SilverHackeron November 03 2007 - 11:10:31
Very nice Article bro. That's an awesome rating from me Grin
Malson November 04 2007 - 13:44:21
Recursion*
ynori7on November 04 2007 - 18:48:38
whoops
Post Comment

Sorry.

You must have completed the challenge Basic 1 and have 100 points or more, to be able to post.