Recursive + stack space...

Post #121,743 by admin 10/17/03 5:30:56 PM Reply	Recursive + stack space... One of Bryce's requirements was that a recursive algorithm not be used, in order to allow for the iteration of very large character spaces. Honestly, though, I typically find recursive algorithms to be more opaque to quick understanding than iterative algorithms. This probably has something to do with my dislike of LISP. ;-) Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,747 by JimWeirich 10/17/03 6:31:32 PM Reply	Re: Recursive + stack space... One of Bryce's requirements was that a recursive algorithm not be used Actually, the statement was "rather not try recursion because the stack could get too deep". In this algorithm, the recursion depth is bounded by the length of the string, so stack depth is not a problem. (The example string only needs a stack depth of 4). Regarding the understanding of recursive algorithms, I can't help you there. I often find the opposite to be true. -- -- Jim Weirich jweirich@one.net [link\|http://onestepback.org\|http://onestepback.org] --------------------------------------------------------------------- "Beware of bugs in the above code; I have only proved it correct, not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)
Post #121,832 by admin 10/18/03 1:15:01 PM Reply	Ah, ok. See what I mean about finding recursion opaque? :-) Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,834 by deSitter 10/18/03 1:28:31 PM Reply	Proof by induction Ever formally been through this? Say one has a proposition that depends on an integer. 1) Let the proposition be manifestly true for K=1. 2) Assume the proposition is true for K. If 1) and 2) imply that the proposition is true for K+1, then it's true for any K. Example: Proposition: 1+2+...+N = 1/2(N+1)N 1) Clearly true for N=1. 2) Assume 1+2+...+(N-1) = 1/2N(N-1). Then 1+2+...+(N-1)+N = 1/2N(N-1) + N = N(1/2(N-1) + 1) = 1/2N(N+1) So it's true for any N. That's basically all there is to recursion. -drl
Post #121,836 by admin 10/18/03 1:32:39 PM Reply	... I have a degree in algorithmic mathematics. Of course I've been through proof by induction. :-) I know how recursion works, and I can figure it out. However, it doesn't come instantly to understanding. While the same thing might be said for functional programming, I don't have as much of an issue with it for some reason. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,839 by deSitter 10/18/03 1:49:38 PM Reply	(sheepish grimace) Yes, recursion is trivial in APL, the prototype for a functional language. -drl
Post #121,842 by JimWeirich 10/18/03 2:51:28 PM Reply	Recursion and Lisp I had Daniel Friedman (author of the Little Lisper) as a first year CS instructor in college. The class was supposed to be an introduction to FORTRAN (that dates me!). But when I went to class, Prof. Friedman kept writing code on the board that had way too many parenthesis for FORTRAN. I spent about three days in class absolutely confused and lost. Around the third day understanding dawned and recursion (and LISP) started making a lot of sense. Its a powerfull tool to have on your workbench. If you ever come across a copy of the Little Lisper (or Little Schemer), its a fairly gentle way to become comfortable with recursion (and a lot of other ideas). The books are written in a style that's not too different from the way Friedman teaches. -- -- Jim Weirich jweirich@one.net [link\|http://onestepback.org\|http://onestepback.org] --------------------------------------------------------------------- "Beware of bugs in the above code; I have only proved it correct, not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)
Post #121,845 by admin 10/18/03 3:31:03 PM Reply	You still misunderstand me. I'm perfectly comfortable reading and writing recursive code. I just don't find it the easiest code for immediate understanding. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."
Post #121,853 by deSitter 10/18/03 8:05:14 PM Reply	Re: You still misunderstand me. Well, I think it probably is psychologically harder, because in the back of your mind you're worrying about the recursion converging. -drl
Post #121,850 by FuManChu 10/18/03 5:34:05 PM Reply	Only other people's... :) I find it very natural, understandable, and quick to write them; reading one created by someone else is another story; it takes a certain amount or style of documentation to make it easier. This probably has something to do with my dislike of LISP. ;-) Been following the world-record-for-crossposting thread on comp.lang.python + comp.lang.lisp? "Python syntax in Lisp and Scheme" and now "Why don't people like lisp?" Entertaining stuff. "There's a set of rules that anything that was in the world when you were born is normal and natural. Anything invented between when you were 15 and 35 is new and revolutionary and exciting, and you'll probably get a career in it. Anything invented after you're 35 is against the natural order of things." Douglas Adams
Post #121,858 by admin 10/18/03 9:20:21 PM Reply	No, I should go look that one up. Regards, -scott anderson "Welcome to Rivendell, Mr. Anderson..."

Welcome to IWETHEY!