preemptive recursive algorithm be tail recursive as well?
By definition:
Non-Premptive Recursion : if a function calls itself from one of its parameters then such a recursion is called Non-Premptive Recursion. Example: Ackermann's function is an example of Non-Preemptive Recursion
private static int Foo(int i)
{
if (i == 1000000)
return i;
if (i % 100 == 0)
Console.WriteLine(i);
return Foo(Foo(i+1));//last statement of the function
}
Here the recursive call to Foo is the last statement of the function and is not part of an expression which makes it a tail recursive call. But on the other hand since the Foo function has been called as an argument so it will result in creation of call stack frames which can't be discarded until the termination condition has been reached.
In tail recursion, compiler can optimize the tail recursion calls as it need not maintain the call stack frames. So my question is that - Is my recursive call to Foo in the above code snippet really a tail recursive call?
Can a non-preemptive recursive algorithm be tail recursive as well?
Yes.
Is my recursive call to Foo in the above code snippet really a tail recursive call?
Which one? There are two recursive calls:
…(Foo(i+1))… - not tail-recursive return Foo(…); - tail-recursive The outer, tail-recursive one can be optimised:
private static int Foo(int i) {
while (i != 1000000) {
if (i % 100 == 0) Console.WriteLine(i);
i = Foo(i+1);
}
return i;
}
The compiler may deduce that Foo always returns 1000000 (if it returns), and therefore further rewrite the method to another tail-recursion, but that requires advanced reasoning and is not a simple transformation:
private static int Foo(int i) {
if (i != 1000000) {
if (i % 100 == 0) Console.WriteLine(i);
} else {
return i;
}
return Foo(i+1);
}
which then can be transformed by the tail-recursion rule into
private static int Foo(int i) {
while (i != 1000000) {
if (i % 100 == 0) Console.WriteLine(i);
i = i+1;
}
return i;
}
上一篇: 斯卡拉尾递归
下一篇: 抢先递归算法是否也是递归的？