Author: Dan Andersson
Date: 11:41:20 04/11/04
Go up one level in this thread
On April 11, 2004 at 14:06:03, Vincent Diepeveen wrote: >On April 10, 2004 at 10:29:51, Dan Andersson wrote: > >> There are reasons for using recursion. One of them is that the generated code >>tends to be smaller. And that could trumph any gains made from reducing the > >I disagree with the first point with regards to the data used by the processor >on the stack. In my function ABISMP() which is a non recursive search using >principal variation search, i never call the function ABISMP() again. I just >call it 1 time. That reduces data overhead considerable. It's faster too. > >That it is a bit more work to get it to work than recursive search i agree with. >Complex code can be very tiny though. > It could be. But in practice compilers have a hard time reducing code while keeping enough information to do high level optimizations. So it is a YMMV issue. >>data. >> Another one is decreasing complexity. And the ability to use induction to prove >>an algorithm. > >Search algorithms are so complex that it is very hard to proof anything >theoretically. I'm using extensions (singular also) which are of course in fact >related to the complex evaluation function and nullmove with a quiescencesearch >which also is unlimited in fact for checks (stack limits it to 32 ply). > >In short try to proof something about that. In general your proof has nothing to >do with whether it is recursive or non-recursive. > Wile it is true in theory it is in most cases significantly easier to reason and perform proofing on sane recursive code. >> I often use tail recursion as a goto with values. It usually doesn't incur any >>overhead. And increases branch prediction for some types of code like parsers, > >Calling functions is very expensive. I do not know how low level you program but >a function call a few years ago for commercial chessprograms was too expensive. > Funny how you should group that comment close to my mention of tail recursion. Because you should know that tail recursion has nothing to do with function calls at low level code. >Ask whether one of the commercial programs at the time used recursion. The >answer is NO. > >>regexp and interpreters. > >It's all high level stuff used to learn students how things work. Not how >reality works. > Also a funny commentary. Recursion and self similarity is in fact a natural occurrence. So it is very real. >Recursion is a good tool to teach students how to do bugfree programming. > >Saying it is faster than other methods is however not true. The call + ret in >assembly is very expensive. > Recursion could very well be faster. The issues of code complexity and the interaction with a Harvard architecture split data/code cache makes it a case of testing to see what works best for you. YMMV as it is. >>MvH Dan Andersson
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.