這些Pascal三角函數是如何工作的？

Question

我在讀Concepts, Techniques, and Models of Computer Programming，開始時有一段代碼，無論我多麼努力，我都無法理解。

declare Pascal AddList ShiftLeft ShiftRight 

fun {Pascal N} 
    if N==1 then [1] 
    else 
     L in 
     L = {Pascal N-1} % Recursion 
     {AddList {ShiftLeft L} 
       {ShiftRight L}} 
    end 
end 

fun {ShiftLeft L} 
    case L of H|T then 
     H|{ShiftLeft T} % Recursion 
    else [0] 
    end 
end 

fun {ShiftRight L} 
    0 | L 
end 

fun {AddList L1 L2} 
    case L1 of H1|T1 then 
     case L2 of H2|T2 
     then 
    H1+H2|{AddList T1 T2} % Recursion 
     end 
    else nil 
    end 
end 

我種得到的語言結構（這是介紹），但真正站在我的方式就是遞歸。

我試圖在每個遞歸調用上放一個標籤，它會抽象地說出這裏發生了什麼，但我無法弄清楚。

我要求的是對這些功能如何工作的清晰和簡單的解釋。

Answer 1

以N == 1開頭：這很簡單。結果只是[1]。

現在檢查對於N == 2：

First we calculate L = {Pascal N-1} = {Pascal 2-1} = {Pascal 1} = [1] 
Now shifted to the left: [1 0] 
Shifted to the right: [0 1] 
AddList just adds elementwise. So the result for {Pascal 2} is [1 1]. 

現在對於N個== 3：

{Pascal 2} = [1 1] 
Shifted left: [1 1 0] 
Shifted right: [0 1 1] 
Added:   [1 2 1] 

當然各地的方案工作的其他方式：它開始與一些較大的N。但在Pascal函數開始時，程序重複遞歸，直到參數N變爲1。這樣的事情：

{Pascal 3} 
    {Pascal 2} 
     {Pascal 1} 
     [1] 
    [1 1] 
[1 2 1] 

編輯：實際上有種類的遞歸在程序中。 Pascal中的第一個以一些整數N開始，遞歸到1。

另一種方法（在輔助方法中）從包含頭部和尾部的列表開始，並且一旦列表爲空即停止，即不能再分割。 （這是使用所謂的缺點清單，一種固有的遞歸數據類型。）