兩個鏈接列表的總和

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 
}