将递归转换为尾递归? [英] Transforming recursion into tail recursion?

问题描述

我正在尝试编写一个递归地找到某个数字的n次方的谓词 [A ^ n = A * A ^(n-1)]，并使用快捷方式A ^(2n)= A ^ n * A ^ n.

I am trying to write a predicate that recursively finds the nth power of some number [A^n = A * A^(n-1)] and uses the shortcut A^(2n) = A^n * A^n.

到目前为止，这是解决方案.

Here is the solution so far.

p(_,0,1):-!.
p(A,N,R):-N mod 2=0,!,N1=N/2,p(A,N1,R1),R=R1*R1.
p(A,N,R):-N1=N-1,p(A,N1,R1),R=R1*A.

现在，我要使此尾递归.在没有捷径的情况下(例如添加乘积器)，我可以在一些简单的情况下进行尾部分析，例如阶乘和幂，但这很难.

Now I want to make this tail recursive. I can do tail for simple cases, such as factorials and power without the shortcut (by adding an accumulator), but this one is hard.

非常感谢您的帮助！

推荐答案

似乎毕竟有可能，只需从另一端开始即可.

It seems it is sort of possible after all, just start it from the other end:

pow(A,N,R) :-
    pow(A,N,A,1,R).

pow(_,N,R,N,R) :- !.
pow(A,N,Acc,M,R) :-
    M =< N div 2, !,
    M1 is M*2,
    NewAcc is Acc * Acc,
    pow(A,N,NewAcc,M1,R).
pow(A,N,Acc,M,R) :-
    M < N,
    M1 is M+1,
    NewAcc is A * Acc,
    pow(A,N,NewAcc,M1,R).

它将快捷方式应用到小于N的2的最高幂，这与算法的工作方式是不一样的.

It applies the shortcut up to the highest power of 2 smaller than N, which is admittedly not the same as what your algorithm is doing.

这篇关于将递归转换为尾递归?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！