两个链接列表的总和

Question

一个类Nat通过指定n-1个数的前置字段表示一个Number（n），如果pre为null，则表示该数为零。

public class Nat { 

    private final Nat pre; 
    public Nat (Nat pre) { this.pre = pre; } 
    public Nat() { this(null); } 
    public boolean isZero() { return pre == null; } 
    public Nat succ() { return new Nat(this); } 

    … 
    } 

，我要补充这两个数相加的方法，我不明白这是如何想返回一个纳特表示的“本”之等！

public Nat plus (Nat other) { 

if (other.isZero()) 
return this; 

return succ().plus(other.pre); 
} 

我认为它会创建一个“纳茨”，它指向的这个（前）所有的时间第二纳特.. 可以在任何一个可以帮助我吗？

Answer 1

好吧，如果this代表n和other代表m，计算n + m是equivant来计算n+1 + m-1，这正是succ().plus(other.pre)回报。

在recurssion结束时，第一个数字达到n+m，第二个数字达到0。这就是为什么当other.isZero()为真时返回this。

Answer 2

您没有在列表中直接存储的数字，并递归创建：

1. [空] - > 0
2. [空 - > NAT1（预= NULL）〕 - > 1
3. [空 - > NAT1（预= NULL） - > NAT2（预= NAT1）〕 - > 2
4. 等

为什么加号（）的工作原理：

现在我们可以看到，增加x+y可以更改为(x-1)+(y+1)等，直到0 + (y + x)。在你的代码中，你本身对增加本身并不感兴趣，但是你想得到代表总和结果的Nat。你这样做递归使用上述改造，直到other是0 - 这是一个简单的计算递归调用，并确保你做他们x倍的基本情况。

例子：

[null -> Nat1(pre=null) -> Nat2(pre=Nat1) -> Nat3(pre=Nat2) -> Nat4(pre=Nat3) -> Nat5(pre=Nat5)] 

而且我们说你要添加3和2。首先，你开始other=Nat2，并调用它Nat3，让您得到Nat3's继任者是Nat4和使用other's前身是Nat1，仍然没有零调用它plus()所以你Nat1's前身是null呼吁plus()上Nat4's继任者（Nat5） ，你打你的基本情况，并返回this这在递归这一点是Nat5。

Answer 3

• 它类似于尾递归

基本上它解开等式

n + k = (n + 1) + (k - 1) 

直到k是零。在这个过程中，创造了很多临时性的Nats，但最终的结果是Nat在另一个Nat加数为零的情况下：你在第一个Nat中积累了结果。写下所有调用的算法的简单执行，您将看到它。

例子：1 + 2

1.plus(2) 
-- 1.succ().plus(1) 
---- 1.succ().succ().plus(0) 
------> 1.succ().succ() == 3 

编辑：违背其他职位，我认为这是不严格地说递归递归。实际上，plus（）方法并不总是在同一个对象实例上调用。但行为确实是递归的。那么它取决于你的定义

Answer 4

这种递归在功能语言中更容易理解。

我确定其他帖子对于plus足够清晰（a+b变为a+1+b-1）。

什么它必须明确的是与此相关的部分：

public Nat (Nat pre) { this.pre = pre; } 
... 
public Nat succ() { return new Nat(this); } 

当succ()被调用，它返回一个新的对象，从这里这么this：

public Nat succ() { return new Nat(this); } 

将pre从这里：

public Nat (Nat pre) { this.pre = pre; } 

这就是为什么t帽子succ的作品，因为最后会有类似this.pre.pre....pre的东西。

为了更好的理解，你可以输入这个（最终添加一些打印线在你的方法）：

public static void main(String[] args) { 
    System.out.println("==== A new number is 0 ===="); 
    Nat n1 = new Nat();     // 0 
    System.out.println(n1.isZero()); // true 
    Nat n2 = new Nat();     // 0 
    System.out.println(n2.isZero()); // true 
    Nat sum = n1.plus(n2);    // 0 
    System.out.println(sum.isZero()); // true 
    System.out.println(n2.isZero()); // true 
    System.out.println("==== Test succ and pre ===="); 
    Nat one = n1.succ();    // 1 
    System.out.println(one.isZero()); // false 
    Nat two = one.plus(one);   // 1 + 1 
    System.out.println(two.isZero()); // false 
    System.out.println(two.pre.isZero());  // false 
    System.out.println(two.pre.pre.isZero()); // true 
}