algorithm - recursive - tail recursion好處




什麼是尾遞歸? (15)

在開始學習lisp的同時,我遇到了tail-recursive這個術語。 這究竟意味著什麼?


尾遞歸是遞歸函數,其中函數在遞歸調用返回後不進行計算的函數的末尾(“尾”)調用自身。 許多編譯器會優化以將遞歸調用更改為尾遞歸或迭代調用。

考慮計算階乘的問題。

一個簡單的方法是:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

假設你稱之為階乘(4)。 遞歸樹將是:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

在上述情況下的最大遞歸深度是O(n)。

但是,請考慮以下示例:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

factTail(4)的遞歸樹將是:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

在這裡,最大遞歸深度是O(n),但是沒有一個調用將任何額外的變量添加到堆棧中。 因此,編譯器可以取消堆棧。


Lua編程 ”一書的摘錄顯示瞭如何進行適當的尾遞歸 (在Lua中,但也適用於Lisp)以及為什麼它更好。

尾部呼叫 [尾遞歸]是一種打扮成呼叫的轉移。 當一個函數調用另一個函數作為其最後一個動作時會發生尾部調用,所以它沒有其他任何操作。 例如,在下面的代碼中,對g的調用是尾部調用:

function f (x)
  return g(x)
end

f調用g ,它沒有別的事可做。 在這種情況下,當被調用函數結束時,程序不需要返回到調用函數。 因此,在尾部調用之後,程序不需要保存關於棧中調用函數的任何信息。 ...

由於正確的尾部調用不使用堆棧空間,因此對程序可以進行的“嵌套”尾部調用的數量沒有限制。 例如,我們可以使用任何數字作為參數來調用以下函數; 它永遠不會溢出堆棧:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

......正如我剛才所說,尾巴呼叫是一種跳轉。 因此,Lua中適當的尾部調用非常有用的應用是編程狀態機。 這些應用程序可以通過函數來表示每個狀態; 改變狀態是去(或去呼叫)一個特定的功能。 作為一個例子,讓我們考慮一個簡單的迷宮遊戲。 迷宮有幾個房間,每個房間最多有四個門:北,南,東,西。 在每一步,用戶輸入一個移動方向。 如果有朝這個方向的門,用戶就去相應的房間; 否則,程序會打印警告。 目標是從最初的房間到最後的房間。

這個遊戲是一個典型的狀態機,當前房間是狀態。 我們可以為每個房間實現這種迷宮功能。 我們使用尾巴呼叫從一個房間移動到另一個房間。 有四間房間的小型迷宮可能是這樣的:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

所以你看,當你做一個遞歸調用時:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

這不是尾遞歸,因為在遞歸調用之後,您仍然需要在該函數中執行(添加1)。 如果輸入的數字非常大,可能會導致堆棧溢出。


傳統的遞歸中 ,典型的模型是先執行遞歸調用,然後獲取遞歸調用的返回值併計算結果。 以這種方式,直到您從每次遞歸調用返回後,才會得到計算結果。

尾遞歸中 ,首先執行計算,然後執行遞歸調用,將當前步驟的結果傳遞給下一個遞歸步驟。 這導致最後一條語句的形式是“(return(recursive-function params))”(我認為這是Lisp的語法)。 基本上,任何給定的遞歸步驟的返回值都與下一個遞歸調用的返回值相同

這樣做的結果是,一旦準備好執行下一個遞歸步驟,就不再需要當前的堆棧幀。 這允許一些優化。 事實上,使用適當的編譯器,你不應該有一個帶有尾遞歸調用的堆棧溢出snicker 。 只需重新使用當前的堆棧幀進行下一個遞歸步驟即可。 我很確定Lisp會這樣做。


在Java中,這裡有一個可能的斐波那契函數的尾遞歸實現:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

將其與標準的遞歸實現進行對比:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

尾遞歸是你現在生活的生活。 你一再重複使用同一個堆棧幀,因為沒有理由或方法返回到“前一個”幀。 過去已經結束,所以可以放棄。 你會得到一個框架,永遠走向未來,直到你的過程不可避免地死去。

當您考慮某些進程可能使用額外的幀時,類比就會崩潰,但如果堆棧不能無限增長,仍然被視為尾遞歸。


我不是Lisp程序員,但我認為this會有所幫助。

基本上這是一種編程風格,遞歸調用是你做的最後一件事。


理解tail call recursion的最好方法是: tail call recursion的一個特例, 最後一次調用 (或尾調用)是函數本身。

比較Python中提供的示例:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^遞推

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^尾巴回報

正如您在一般遞歸版本中看到的那樣,代碼塊中的最終調用是x + recsum(x - 1) 。 所以在調用recsum方法之後,還有另一個操作是x + ..

然而,在尾遞歸版本中,代碼塊中的最終調用(或尾調用)是tailrecsum(x - 1, running_total + x) ,這意味著最後一次調用是對方法本身進行的,並且之後沒有任何操作。

這一點很重要,因為這裡看到的尾遞歸不會使內存增長,因為當底層VM看到一個函數調用自己在尾部位置(函數中最後一個要評估的表達式)時,它消除了當前的棧幀,被稱為尾巴呼叫優化(TCO)。

編輯

NB。 請記住,上面的示例是用Python運行時不支持TCO的Python編寫的。 這只是一個例子來解釋這一點。 像Scheme,Haskell等語言支持TCO


簡而言之,尾遞歸將遞歸調用作為函數中的最後一個語句,以便它不必等待遞歸調用。

所以這是一個尾遞歸,即N(x-1,p * x)是函數中的最後一個語句,編譯器很聰明地發現它可以優化為for循環(階乘)。 第二個參數p帶有中間產品值。

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

這是編寫上述因子函數的非尾遞歸方法(儘管一些C ++編譯器可能能夠優化它)。

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

但這不是:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

我寫了一篇很長的文章“ 理解尾遞歸 - Visual Studio C ++ - Assembly View


這個問題有很多很好的答案......但我不禁要問,如何定義“尾遞歸”,或者至少是“適當的尾遞歸”。 也就是說:應該將它看作程序中特定表達式的屬性嗎? 還是應該把它看作是編程語言實現的一個屬性?

關於後一種觀點的更多信息,Will Clinger在“Proper Tail Recursion and Space Efficiency”(PLDI 1998)中提供了一篇經典paper ,將“適當的尾部遞歸”定義為編程語言實現的一個屬性。 該定義的構造允許忽略實現細節(例如調用堆棧實際上是通過運行時堆棧還是通過堆分配的鏈接列錶框)。

為了實現這一點,它使用漸近分析:不像通常看到的程序執行時間,而是程序空間使用率 。 這樣,堆分配的鏈接列表與運行時調用堆棧的空間使用最終漸近等價; 所以人們會忽略那些編程語言實現細節(這個細節在實踐中確實很重要,但是當試圖確定某個給定的實現是否滿足“屬性尾遞歸”的要求時,可能會淹沒水域, )

這篇論文值得仔細研究,原因如下:

  • 它給出了程序的尾部表達尾部調用的歸納定義。 (這樣一個定義,以及為什麼這樣的呼叫很重要,似乎是這裡給出的大多數其他答案的主題。)

    以下是這些定義,只是為了提供一些文字的味道:

    定義1以核心方案編寫的程序的尾部表達式如下歸納定義。

    1. lambda表達式的主體是尾部表達式
    2. 如果(if E0 E1 E2)是尾部表達式,那麼E1E2都是尾部表達式。
    3. 沒有別的是尾巴表達。

    定義2 尾調用是一個過程調用的尾部表達式。

(尾遞歸調用,或者如文件所述,“自尾調用”是調用本程序的尾調用的特例。)

  • 它為評估核心方案提供了六種不同“機器”的正式定義,其中每台機器具有相同的可觀察行為, 除了每個機器所處的漸近空間複雜度類別之外

    例如,在分別給出機器的定義之後,1.基於堆棧的內存管理,2.垃圾回收但沒有尾部調用,3.垃圾回收和尾部調用,本文繼續使用更先進的存儲管理策略,例如4.“evlis尾遞歸”,其中在尾調用中評估最後一個子表達式參數時不需要保留環境,5.將閉包的環境僅僅減少到閉包的自由變量,以及6. Appel和Shao定義的所謂“安全空間”語義。

  • 為了證明這些機器實際上屬於六個不同的空間複雜性類別,本文針對每一對比較的機器提供了一些程序的具體示例,這些程序將在一台機器上暴露漸進式空間爆炸,而另一台則沒有。

(現在閱讀我的答案,我不確定我是否能夠實際捕捉到paper的關鍵點,但是,現在我無法花更多時間來開發這個答案。)


這意味著,不需要將指令指針壓入堆棧,只需跳到遞歸函數的頂部並繼續執行即可。 這允許函數無限期遞增而不溢出堆棧。

我寫了blog關於這個主題的blog文章,裡面有堆棧框架的圖形例子。


這是一個比較兩個函數的快速代碼片段。 第一個是傳統遞歸,用於查找給定數字的階乘。 第二個使用尾遞歸。

非常簡單直觀的理解。

簡單的方法來判斷一個遞歸函數是否是遞歸函數,如果它返回基本情況下的具體值。 這意味著它不會返回1或者真的或類似的東西。 它將更可能返回某個方法參數的某個變體。

另一種方法是告訴是遞歸調用是否沒有任何附加,算術,修改等等......僅僅意味著一個純粹的遞歸調用。

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

這是關於尾遞歸的計算機程序結構和解釋摘錄。

在迭代和遞歸的對比中,我們必須注意不要將遞歸過程的概念與遞歸過程的概念相混淆。 當我們將過程描述為遞歸時,我們指的是過程定義引用(直接或間接)過程本身的語法事實。 但是當我們將一個流程描述為遵循線性遞歸的模式時,我們正在談論流程如何演變,而不是關於如何編寫流程的語法。 看起來令人不安的是,我們將一個遞歸過程(例如fact-iter)稱為生成一個迭代過程。 然而,這個過程真的是迭代的:它的狀態完全被它的三個狀態變量捕獲,並且解釋器只需要追踪三個變量來執行該過程。

流程和過程之間的區別可能會造成混淆的一個原因是,大多數通用語言(包括Ada,Pascal和C)的實現都是這樣設計的,即任何遞歸過程的解釋都會消耗大量的隨著過程調用的數量,即使所描述的過程原則上是迭代的。 因此,這些語言只能通過諸如do,repeat,until,for和while等特殊用途的“循環結構”來描述迭代過程。 計劃的實施不會分享這個缺陷。 它將在恆定空間中執行迭代過程,即使迭代過程由遞歸過程描述。 具有此屬性的實現稱為尾遞歸。 通過尾遞歸實現,可以使用普通的過程調用機制來表達迭代,因此特殊的迭代構造只能用作語法糖。


這裡是前面提到的tailrecsum函數的Perl 5版本。

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

遞歸意味著一個自己調用的函數。 例如:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

尾遞歸意味著結束函數的遞歸:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

請參閱最後一件未結束的函數(在Scheme術語中,過程)是調用它自己。 另一個(更有用的)例子是:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

在輔助程序中,如果離開的最後一件事情不是零,那就是自己調用它(在某件事情和某件事情發生後)。 這基本上就是你如何映射一個列表。

尾遞歸具有很大的優勢,即interperter(或編譯器,依賴於語言和供應商)可以優化它,並將其轉換為相當於while循環的東西。 事實上,在Scheme的傳統中,大部分“for”和“while”循環都是以尾遞歸的方式完成的(據我所知,沒有for和while)。


考慮添加前N個整數的簡單函數。 (例如, sum(5) = 1 + 2 + 3 + 4 + 5 = 15 )。

這是一個簡單的使用遞歸的JavaScript實現:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

如果你調用了recsum(5) ,這就是JavaScript解釋器會評估的內容:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

請注意,在JavaScript解釋器開始真正完成計算總和之前,每個遞歸調用都必須完成。

這是一個相同函數的尾遞歸版本:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

以下是如果您調用tailrecsum(5) (由於默認的第二個參數,它實際上是tailrecsum(5, 0) tailrecsum(5)會發生的事件序列。

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

在尾遞歸的情況下,每次評估遞歸調用時, running_total被更新。

注意:原始答案使用Python的示例。 這些已被更改為JavaScript,因為現代JavaScript解釋器支持尾部調用優化,但Python解釋器不支持。





tail-recursion