Author: Omid David Tabibi
Date: 02:19:25 09/15/03
Go up one level in this thread
On September 15, 2003 at 04:22:27, Uri Blass wrote:
>On September 15, 2003 at 03:40:39, Omid David Tabibi wrote:
>
>>On September 15, 2003 at 00:04:21, Uri Blass wrote:
>>
>>>Can programmers write a program that take a code with recursive functions and
>>>translate it to a code without recursive functions that does the same thing?
>>>
>>>Do not answer me that the compiler does it by translating it to assembler
>>>because the translation should be done to a program in the same computer
>>>language so a C source should be translated to another C source.
>>>
>>
>>The problem has nothing do with C, since it is an algorithmic issue. Translating
>>a tail-recursion into an iterative version is usually easy (actually, in some
>>cases tail-recursions are already translated into iterative versions by the
>>compiler). But non-tail-recursions are quite hard to translate into iterative
>>versions. It is especially hard to find a non-recursive implementation for DFS.
>
>what is tail recursion
There are two types ofrecursions, one that you have the result already when you
are at the deepest level, and the other one when the result is backed up and
used for further calculations.
The following is not tail recursion, because the result returned from calling
factorial() is used for further computations.
int factorial(int n) {
if (n == 0)
return 1;
return n * factorial(n - 1);
}
The tail-recursion version would be:
int _factorial(int n, int acc) {
if (n == 0)
return acc;
return _factorial(n - 1, n * acc);
}
int factorial(int n) {
return _factorial(n, 1);
}
Which can be easily translated into an iterative version (even by the compiler):
int factorial(int n) {
for (int acc = 1; n != 0; n--)
acc *= n;
return acc;
}
>and what is DFS?
Depth First Search. AlphaBeta is an example of a depth first search. The other
basic search algorithm is breadth first search (BSF).
The difference is that in the following tree:
1
/ \
2 3
/ \ / \
4 5 6 7
DFS will search in the order: 1-2-4-5-3-6-7
BFS will search in the order: 1-2-3-4-5-6-7
>
>I thought about the option to translate my alphabeta to a non recursive version.
>
You first have to find an iterative implementation of DFS, which is not an easy
task.
>I guess that it is done by the compiler
A good compiler will translate only the very basic tail-recursions into an
iterative version. Again, AlphaBeta is not tail-recursion (and of course not
basic :)
>but today I cannot call the value of a
>varaible from a previous iteration of alpha beta without saving it in a global
>array first and I think that it is a waste of space.
>
>Maybe it is an easy task but I did not think exactly how to do it and prefered
>to do other things in the program.
>
>I do it in my perft function but it is simpler because there is a fixed number
>of iterations.
>
>In my alpha beta I may extend more than 1 ply in some situations and I do not
>know if it can cause a problems in the translation to non recursive function.
>
>I guess that it can be done by a loop but I still did not think exactly how to
>do it so I have no idea how much time it takes to change it.
>
>
>Uri
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.