複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/遞歸算法/4323575
複製
複製成功

遞歸算法

鎖定
遞歸算法（recursive algorithm [4]  、recursion algorithm [5]  ）在計算機科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函數編程語言（如Scheme）中習慣用遞歸來實現循環。
中文名
遞歸算法
外文名
recursive algorithm [4] 
recursion algorithm [5] 
屬    性
計算機算法
實現過程
一般通過函數或子過程來實現
特    點
遞歸就是在過程或函數里調用自身

目錄

  1. 1 簡介
  2. 2 遞歸程序
  3. ▪ 不動點組合子
  4. ▪ 尾部遞歸
  5. 3 能夠解決的問題
  6. 4 遞歸數據

遞歸算法簡介

遞歸算法應用的場景是要解決的問題和其子問題具有相似性的時候，通過直接或間接的調用自己求出問題解的方法。它是通過解決一個問題的更小實例來解決一個大的問題的解的算法。遞歸算法有兩個過程，一是調用過程，二是向上傳遞結果的過程。 [3] 

遞歸算法遞歸程序

在支持自調用的編程語言中，遞歸可以通過簡單的函數調用來完成，如計算階乘的程序在數學上可以定義為：
這一程序在Scheme語言中可以寫作：
(define (factorial n)  (if (= n 0)      1      (* n (factorial (- n 1)))))

遞歸算法不動點組合子

即使一個編程語言不支持自調用，如果在這語言中函數是第一類對象（即可以在運行期創建並作為變量處理），遞歸可以通過不動點組合子（英語：Fixed-point combinator）來產生。以下Scheme程序沒有用到自調用，但是利用了一個叫做Z 算子（英語：Z combinator）的不動點組合子，因此同樣能達到遞歸的目的。
(define Z  (lambda (f)    ((lambda (recur) (f (lambda arg (apply (recur recur) arg))))     (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact  (Z (lambda (f)       (lambda (n)         (if (<= n 0)             1             (* n (f (- n 1))))))))
這一程序思路是，既然在這裏函數不能調用其自身，可以用 Z 組合子應用(application)這個函數後得到的函數再應用需計算的參數。

遞歸算法尾部遞歸

尾部遞歸是指遞歸函數在調用自身後直接傳回其值，而不對其再加運算。尾部遞歸與循環是等價的，而且在一些語言（如Scheme中）可以被優化為循環指令。 因此，在這些語言中尾部遞歸不會佔用調用堆棧空間。以下Scheme程序同樣計算一個數字的階乘，但是使用尾部遞歸： [1]  
(define (factorial n)  (define (iter product counter)    (if (> counter n)        product        (iter (* counter product)              (+ counter 1))))  (iter 1 1))

遞歸算法能夠解決的問題

  1. 數據的定義是按遞歸定義的。如Fibonacci函數。
  2. 問題解法按遞歸算法實現。如Hanoi問題。
  3. 數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。

遞歸算法遞歸數據

數據類型可以通過遞歸來進行定義，比如一個簡單的遞歸定義為自然數的定義：“一個自然數或等於0，或等於另一個自然數加上1”。Haskell中可以定義鏈表為：
data ListOfStrings = EmptyList | Cons String ListOfStrings
這一定義相當於宣告“一個鏈表或是空串列，或是一個鏈表之前加上一個字符串”。可以看出所有鏈表都可以通過這一遞歸定義來達到。 [2] 
參考資料
  • 1.    Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs. Cambridge, MA: MIT Press. 1996 [2011]. ISBN 0-262-01153-0
  • 2.    Graham, Ronald; Donald Knuth, Oren Patashnik. Concrete Mathematics. 1990. Chapter 1: Recurrent Problems
  • 3.    胡昆鵬,仵子俊.分治遞歸算法的解題能力[J].電腦編程技巧與維護,2023(1):44-47
  • 4.    張孟常．設計概論新編 增補版：上海人民美術出版社，2021.10：174
  • 5.    喜超，高儼，譚雅青編著．C#面向對象程序設計：雲南科技出版社，2021.09：71