SICP 2.64遞歸過程的增長順序

Question

我是自學的SICP，很難找到遞歸函數的增長順序。

以下程序列表 - >樹的有序列表轉換爲平衡查找樹：

(define (list->tree elements) 
    (car (partial-tree elements (length elements)))) 

(define (partial-tree elts n) 
    (if (= n 0) 
     (cons '() elts) 
     (let ((left-size (quotient (- n 1) 2))) 
     (let ((left-result (partial-tree elts left-size))) 
      (let ((left-tree (car left-result)) 
       (non-left-elts (cdr left-result)) 
       (right-size (- n (+ left-size 1)))) 
      (let ((this-entry (car non-left-elts)) 
        (right-result (partial-tree (cdr non-left-elts) 
               right-size))) 
       (let ((right-tree (car right-result)) 
        (remaining-elts (cdr right-result))) 
       (cons (make-tree this-entry left-tree right-tree) 
         remaining-elts)))))))) 

我一直在尋找解決方案在線，和下面的網站，我相信提供了最佳的解決方案，但我有它的麻煩決策意識：

jots-jottings.blogspot.com/2011/12/sicp-exercise-264-constructing-balanced.html

我的理解是，這一程序「部分樹」重複調用每個被調用時，以上三個參數 - 「這個條目」，「左樹」和「右樹'尊重沉着應對。 （和「剩餘的ELT」只有當它是必要的 - 無論是在最初的「分樹」打電話或當「非左應急定位發射器」的叫法）

1. 這個條目來電：汽車，CDR， cdr（left-result）
2. 左輸入呼叫：car，cdr和其長度減半的每一步
3. 右輸入呼叫：car，cdr自身（cdr（left-result））作爲參數和長度減半

'left-entry'將有2個log（n）個步驟，所有三個參數分別調用'left-entry'。 所以它會有三元樹狀結構和我認爲會類似於3^log（n）的步驟總數。但解決方案說它只使用每個索引1..n只有一次。但是，例如，'this-entry'是否會在與「右入門」分離的每個節點上減少相同的索引？

我很困惑.. 此外，在部分（A）的溶液網站指出：

「在非終止情況下的部分樹首先計算應該進入的元素個數 然後調用具有元素的部分樹和 值，這兩個值都在該子樹中生成這樣的子樹並且不是 的元素列表。未使用元素的頭部爲當前節點的 值「

我相信該過程在左樹之前執行this-entry。爲什麼我錯了？

這是我第一本關於CS的書，我還沒有碰到主定理。 在某些解決方案中提到了它，但希望我應該能夠在不使用它的情況下執行該問題。

謝謝您的閱讀，我期待着您的善意回覆，

克里斯

Answer 1

您需要了解let形式是如何工作的。在

  (let ((left-tree (car left-result)) 
       (non-left-elts (cdr left-result)) 

left-tree不不 「呼」 任何東西。它被創建爲一個新的詞彙變量，並賦值爲(car left-result)。它周圍的括號只是組合在一起描述由let形式引入一個變量的元素：變量的名稱和值：

  (let ( ( left-tree  (car left-result) ) 
      ;;  ^^         ^^ 
        ( non-left-elts (cdr left-result) ) 
      ;;  ^^         ^^ 

---

這裏是如何理解如何的遞歸過程工程：不要。

只是不要試圖瞭解如何它的工作原理;而是分析它的作用，假設它（對於較小的個案例）它應該做什麼。

這裏，(partial-tree elts n)接收兩個參數：元素的列表（可以投入樹，大概）和列表的長度。它返回

  (cons (make-tree this-entry left-tree right-tree) 
        remaining-elts) 

一個缺點對樹的 - 轉換的結果，剩餘的元件，它們應該是無左，在最上面的呼叫，如果長度的論據是正確。

現在，我們知道它應該做什麼，我們看看它。事實上，假設上面所做的事情總是有意義的：將元素數量減半，處理列表，獲取樹和剩餘列表（現在非空），然後處理剩下的內容。

的this-entry是不一棵樹 - 它是裝在一個樹的節點元素：

  (let ((this-entry (car non-left-elts)) 

設置

    (right-size (- n (+ left-size 1)) 

意味着n == right-size + 1 + left-size。這是進入節點本身的1個元素，即this-entry元素。

並且由於每個元素直接進入其節點，所以一次該算法的總運行時間與輸入列表中元素的數量呈線性關係，並使用對數棧空間。