Lisp遞歸問題與堆棧

Question

我剛剛在沿着我的計劃的旅程沿途的另一個顛簸。可以肯定地說，我的桌子已經讓我感到頭痛不已......我已經寫了一個函數，可以在班級作業的列表中找到最小和最大數字。邏輯是健全的（我認爲是這樣），並且一切正常，但是，只有第一個函數調用的值從（define（iterator aList minNum maxNum））返回。我在調試器中注意到，在每次遞歸/函數調用後，我都會看到（使用DrRacket）函數調用被推送到堆棧。一旦遞歸發生在最後一次，並且代碼跳轉到（list minNum maxNum）的返回值，它不會返回它應該的值，因爲我可以看到這些值是正確的，而是我看到函數調用從堆棧中移出一個接一個，直到達到第一個。因此，將返回將成爲列表的前兩個值的初始值。我知道堆棧是FIFO，但是，我甚至沒有試圖將任何東西推入堆棧。理論上我只是想再次調用這個函數，並保持傳遞值......任何有關這方面的指導都將非常感激。

(define (findMinMax aList) 
    (define (iterator aList minNum maxNum) 
    (when(not(null? aList)) 
    (cond 
    ((> minNum (car aList)) 
    (set! minNum (car aList))) 
    ((< maxNum (car aList)) 
    (set! maxNum (car aList)))) 
    (iterator (cdr aList) minNum maxNum)) 
    (list minNum maxNum)) 
(cond ; setting the first two atoms in a list appropriately to the min and max variables. 
((< (car aList) (car(cdr aList))) 
    (iterator (cdr (cdr aList)) (car aList) (car(cdr aList)))) 
((> (car aList) (car(cdr aList))) 
    (iterator (cdr (cdr aList)) (car(cdr aList)) (car aList))) 
(else 
    (iterator (cdr (cdr aList)) (car aList) (car(cdr aList)))))) 

Answer 1

你有計劃細膩度已經比大多數更好在SO！有一個非常有用的Scheme語法關鍵字'named-let'，可以很容易地定義內部的遞歸函數定義。這裏是帶你到一個新的水平的例子：我已經使用了values語法形式返回兩個值

(define (findMinMax list) 
    (assert (not (null? list))) 
    (let finding ((list (cdr list)) 
       (lMin (car list)) 
       (lMax (car list))) 
    (if (null? list) 
     (values lMin lMax) 
     (finding (cdr list) 
       (min lMin (car list)) 
       (max lMax (car list)))))) 

還要注意。而且，我使用了內建函數min和max。此外，finding的使用是尾遞歸的，意思是Scheme編譯器將此遞歸調用轉換爲迭代調用，因此不需要堆棧幀。

Answer 2

你需要重寫代碼不使用任何set!或when因爲它阻礙了你的學習計劃。用Lisp方言寫作時，你必須用不同的方式思考，而不是用Algol方言，所以試着在遞歸中進行改變，而不是使用set!，並使用3種方式if，而只用一個表達式在過程體中。

(define (my-length lst) 
    (define (length-aux lst n) 
    (if (null? lst) 
     n ; base case, return the length 
     (length-aux (cdr lst) (+ n 1)))) ; instead of set! we put the new value as argument 

    (length-aux lst 0)) ; one expression that calls the auxiliary procedure to do the calculations 

你的內部程序，可以製作也很簡單：

(define (iterator aList minNum maxNum) 
    (if (null? <???>) 
     (list minNum maxNum) 
     (iterator <???> 
       (min <???> <???>) 
       (max <???> <???>)))) 

或許與if代替min/max

(define (iterator aList minNum maxNum) 
    (if (null? <???>) 
     (list minNum maxNum) 
     (let ((n (car aList))) ; use n to compare with minNum/maxNum 
     (iterator <???> 
        (if <???> <???> <???>) 
        (if <???> <???> <???>)))) 

Answer 3

你有一些令人誤解的縮進。 1的縮進步驟確實不可取。 2是好的，但是當你學習Scheme時，4更好。

實際上，您只需要進行一些最小的更改，即語法。取而代之的

(define (findMinMax aList) 
    (define (iterator aList minNum maxNum) 
     (when (not (null? aList)) 
      (cond 
       ((> minNum (car aList))   ; change the local 
        (set! minNum (car aList))) ; variable's value 
       ((< maxNum (car aList)) 
        (set! maxNum (car aList)))) 
      (iterator (cdr aList) minNum maxNum)) ; pass new values on, but 
              ; ignore recursive result, and 
     (list minNum maxNum))    ; return the current values instead! 

你需要：

(define (findMinMax aList) 
    (define (iterator aList minNum maxNum) 
     (if (not (null? aList)) 
      (begin 
       (cond 
        ((> minNum (car aList)) 
         (set! minNum (car aList))) 
        ((< maxNum (car aList)) 
         (set! maxNum (car aList)))) 
       (iterator (cdr aList) minNum maxNum)) ; return recursive result! 
      (list minNum maxNum)))     ; ELSE - base case 

最初的電話就是：

(iterator (cdr aList) (car aList) (car aList))) 

Answer 4

是從集走就走！或者你不會學習方案的功能方面的繩索。如果事情非常混亂，你可以使用它，但很少有這種情況。

很多答案下面是遞歸的形式表示，但往往更容易理解的是高階函數

無論是內置的最小值和最大值在一些實現中定義倍的條款。

(define (min first . L) (fold (lambda (x y) (if (< x y) x y)) first L)) 
(define (max first . L) (fold (lambda (x y) (if (> x y) x y)) first L)) 

(define (MinMax first . L) 
    (define (internal y x) 
    (let ((min (car x)) 
      (max (cdr x))) 
     (cons (if (< min y) min y) 
      (if (> max y) max y)))) 
    (fold internal (cons first first) L)) 

請注意，如果您可以適應高階函數的操作，代碼會更清晰。兩條線用於定義ADT，兩條線用於指示摺疊如何沿着本地狀態移動，另一條線用於實際操作。

;;樣品呼叫

> (minmax 0 9 3 4 7 6 -2) 

;Value 4: (-2 . 9)