如何使用递归计算x和y之间的数字总和？

Question

我想请问如何编写一个递归函数，使其能够从起始数字（x）加到结束数字（y）。

例如：summation(Ans, 1, 5)。 答案为15

递归应该计算出 (1+2+3+4+5) = 15。

目前我所做的是：

sumFrom(Sum, X ,Y) :- X>Y, !, write('Start should not be greater than End').
sumFrom(Sum, X ,Y) :- Sum is X+Y,
        Next is X+1,
        sumFrom(Sum, Next, Y).

我对Prolog还很陌生，请温柔点。

- Fight or flight

Answer 1

由于纯（声明子集的）Prolog 没有循环和可变变量，因此执行算术运算可能会很棘手。当基础知识已经清晰时，我认为值得学习库：

?- aggregate(sum(N),between(1,5,N),S).
S = 15.

- CapelliC

---

是的，Barney和Tudor都更加准确。我对他们的好回答没有什么可补充的，但我认为作为新手，您可能会欣赏我的提示，即有大量可用的库... - CapelliC

Answer 2

我有一段时间没有用Prolog了，但是看起来你的程序中没有终止规则：按照现在的写法，程序会一直增加Next，直到它大于Y，然后返回错误条件。所以你需要添加类似以下代码的终止规则：

sumFrom(Sum, X ,Y) :- X=Y, Sum=X.

接下来，您不希望每次都计算“Sum is X + Y”：对于“sumFrom(Ans, 1, 5)”，这将计算1 + 5、2 + 5、3 + 5、4 + 5、5 + 5，每次计算只是替换了上一个值。为了累加总和，您需要计算“Sum is Sum + X”。

最后，我认为您需要一个不同的变量来递归求和，并需要重新排列子句，以便在每个“is”被评估时解决所有相关变量。

因此，您最终得到类似以下内容的东西：

sumFrom(Sum, X ,Y) :- X>Y, !, write('Start should not be greater than End').
sumFrom(Sum, X ,Y) :- X=Y, Sum=X.
sumFrom(Sum, X ,Y) :- Next is X+1,
        sumFrom(Sum1, Next, Y),
        Sum is Sum1+X.

像我说的，对Prolog有点生疏，所以可能不是最好的解决方案，但希望它能有所帮助。

谢谢。

- Barney

Answer 3

一种尾递归的解决方案在堆栈使用方面更高效：

sumFrom(X, Y, Acc, Acc):-
    X > Y, !.
sumFrom(X, Y, Acc, Sum):-
    Acc1 is X + Acc,
    X1 is X + 1,
    sumFrom(X1, Y, Ac11, Sum).

sumFrom(X, Y, Sum):-
    sumFrom(X, Y, 0, Sum).

第一条规则指出，如果 X 大于 Y，那么累加和应该是最终和。如果不是这种情况（即 X =< Y），那么您需要将 X 添加到累加和中，并在尝试满足递归目标之前增加 X。

?- sumFrom(2, 10, Sum).
Sum = 54.

---

注意：上面使用的红色剪切假定sumFrom/4查询中的Sum是自由变量。否则，对于像sumFrom(2, 10, -1)这样的查询，程序可能会无限循环而不是失败。

如果您还想覆盖此类型的查询，请考虑删除红色剪切并将X =< Y条件添加到第二个规则中。

?- sumFrom(2, 10, 55).
false.

?- sumFrom(2, 10, 54).
true ;
false.

- Tudor Berariu

Answer 4

这是一种方法：

sum_of_range(X,X,X) .  % the "sum" of a single-item range is that single item.
sum_of_range(X,Y,S) :- % to get the sum of a multiple item range...
  X < Y ,              % - the lower bound must actually be a lower bound,
  X1 is X+1 ,          % - increment X
  sum(X1,Y,S1) ,       % - compute the sum of that smaller range
  S is X+X1            % - the sum is X + the sum of the smaller range.
  .                    %

如果给定足够大的范围，这将最终导致堆栈溢出。另一种方法是利用尾递归，它有效地将递归转换为迭代（因此可以处理任何大小的范围）：

sum_of_range(X,Y,S) :- sum1(X,Y,0,S) .

sum1(X,X,T,S) :- S is T+X .
sum1(X,Y,T,S) :-
  X < Y ,
  T1 is T+X ,
  X1 is X+1 ,
  sum1(X1,Y,T1,S)
  .

第三种方法可能是构建一个Prolog术语，它是一个算术表达式，并在最后评估它以找到总和：

sum_of_range(X,Y,S) :-    % to sum a range of values...
  summation_term(X,Y,T) , % - construct an arithmetic term
  S is T .                % - and evaluate it.

summation_term(X,X,X) .    % the term for a single value is itself.
summation_term(X,Y,X+T) :- % otherwise...
  X < Y ,                  % - if X is less than Y
  X1 is X+1 ,              % - increment X
  summation_term(X1,Y,T)   % - and recurse down.
  .

你可能会注意到，这并不比像...这样的东西更有用。

findall( N, between(X,Y,N), Ns ) , sumlist(Ns,S)

- Nicholas Carey