fbpx
维基百科

递归 (计算机科学)

十月 20, 2023

遞迴（英語：recursion）在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。[1] 遞迴式方法可以被用於解決很多的電腦科學問題，因此它是電腦科學中十分重要的一個概念。[2] 絕大多數程式語言支援函式的自呼叫，在這些語言中函式可以通過呼叫自身來進行遞迴。計算理論可以證明遞迴的作用可以完全取代迴圈，因此有很多在函數程式語言（如Scheme）中用递归来取代循环的例子。

電腦科學家尼克勞斯·維爾特如此描述遞迴：

遞迴的強大之處在於它允許使用者用有限的語句描述無限的物件。因此，在電腦科學中，遞迴可以被用來描述無限步的運算，儘管描述運算的程式是有限的。

——尼克勞斯·維爾特[3]

遞迴程式 编辑

java 编辑 

public void recursiveTest(){  recursiveTest(); //自己调用自己，就叫递归 }

python 编辑 

def RecursiveTest(): RecursiveTest() # 自己调用自己

以上两个程式是最简单的递归，但因为无限地调用自己而不会停下，就会因为栈空间溢出而导致程序产生异常而强制停止，而python会因为自身设置的保护措施（限定递归的循环次数，但该次数可更改）而不断抛出异常。

所以如果想要设计一个递归程式，就必须注意设定一个表达式判断（例如if语句）来告诉程序是否应该继续递归下去。[4]

应用 编辑

在支援自呼叫的程式語言中，遞迴可以通過簡單的函式呼叫來完成，如計算階乘的程式在數學上可以定義為：

 

這一程式在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程式同樣計算一個數字的階乘，但是使用尾端遞迴：[5]

(define (factorial n)  (define (iter product counter)  (if (> counter n)  product  (iter (* counter product)  (+ counter 1))))  (iter 1 1))

能够解决的问题 编辑

1、数据的定义是按递归定义的。如费氏数列。

2、问题解法按递归算法实现。如汉诺塔。

3、数据的结构形式是按递归定义的。如二叉树、广义表等。

遞迴資料 编辑

主条目：递归数据类型

資料型別可以通過遞迴來進行定義，比如一個簡單的遞迴定義為自然數的定義：「一個自然數或等於0，或等於另一個自然數加上1」。Haskell中可以定義連結串列為： 

data ListOfStrings = EmptyList | Cons String ListOfStrings

這一定義相當於宣告「一個連結串列或是空串列，或是一個連結串列之前加上一個字串」。可以看出所有連結串列都可以通過這一遞迴定義來達到。

参考文献 编辑

  1. ^ Graham, Ronald; Donald Knuth, Oren Patashnik. Concrete Mathematics. 1990. Chapter 1: Recurrent Problems [2011-12-22]. （原始内容于2020-11-06） （英语）. 
  2. ^ Epp, Susanna. Discrete Mathematics with Applications 2nd. 1995: 427 （英语）. 
  3. ^ Wirth, Niklaus. Algorithms + Data Structures = Programs. Prentice-Hall. 1976: 126 （英语）. The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions. 
  4. ^ 廖雪峰. 递归函数. [2018年8月18日11:19:21]. （原始内容于2018年9月24日）. 
  5. ^ Harold Abelson and Gerald Jay Sussman with Julie Sussman. . Cambridge, MA: MIT Press. 1996 [2011]. ISBN 0-262-01153-0. （原始内容存档于2018-03-09） （英语）. 

十月 20, 2023
递归, 计算机科学, 遞迴, 英語, recursion, 在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法, 遞迴式方法可以被用於解決很多的電腦科學問題, 因此它是電腦科學中十分重要的一個概念, 絕大多數程式語言支援函式的自呼叫, 在這些語言中函式可以通過呼叫自身來進行遞迴, 計算理論可以證明遞迴的作用可以完全取代迴圈, 因此有很多在函數程式語言, 如scheme, 中用递归来取代循环的例子, 電腦科學家尼克勞斯, 維爾特如此描述遞迴, 遞迴的強大之處在於它允許使用者用有限的語句描述無限的物件. 遞迴 英語 recursion 在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法 1 遞迴式方法可以被用於解決很多的電腦科學問題 因此它是電腦科學中十分重要的一個概念 2 絕大多數程式語言支援函式的自呼叫 在這些語言中函式可以通過呼叫自身來進行遞迴 計算理論可以證明遞迴的作用可以完全取代迴圈 因此有很多在函數程式語言 如Scheme 中用递归来取代循环的例子 電腦科學家尼克勞斯 維爾特如此描述遞迴 遞迴的強大之處在於它允許使用者用有限的語句描述無限的物件 因此 在電腦科學中 遞迴可以被用來描述無限步的運算 儘管描述運算的程式是有限的 尼克勞斯 維爾特 3 目录 1 遞迴程式 1 1 java 1 2 python 2 应用 2 1 不動點組合子 2 2 尾端遞迴 3 能够解决的问题 4 遞迴資料 5 参考文献遞迴程式 编辑java 编辑 public void recursiveTest recursiveTest 自己调用自己 就叫递归 python 编辑 def RecursiveTest RecursiveTest 自己调用自己以上两个程式是最简单的递归 但因为无限地调用自己而不会停下 就会因为栈空间溢出而导致程序产生异常而强制停止 而python会因为自身设置的保护措施 限定递归的循环次数 但该次数可更改 而不断抛出异常 所以如果想要设计一个递归程式 就必须注意设定一个表达式判断 例如if语句 来告诉程序是否应该继续递归下去 4 应用 编辑在支援自呼叫的程式語言中 遞迴可以通過簡單的函式呼叫來完成 如計算階乘的程式在數學上可以定義為 fact n 1 if n 0 n fact n 1 if n gt 0 displaystyle operatorname fact n begin cases 1 amp mbox if n 0 n cdot operatorname fact n 1 amp mbox if n gt 0 end cases nbsp 這一程式在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 lt n 0 1 n f n 1 這一程式思路是 既然在這裡函式不能呼叫其自身 我們可以用 Z 組合子應用 application 這個函式後得到的函式再應用需計算的參數 尾端遞迴 编辑 主条目 尾端遞迴 尾端遞迴是指遞迴函式在呼叫自身後直接傳回其值 而不對其再加運算 尾端遞迴與迴圈是等價的 而且在一些語言 如Scheme中 可以被優化為迴圈指令 因此 在這些語言中尾端遞迴不會佔用呼叫堆疊空間 以下Scheme程式同樣計算一個數字的階乘 但是使用尾端遞迴 5 define factorial n define iter product counter if gt counter n product iter counter product counter 1 iter 1 1 能够解决的问题 编辑1 数据的定义是按递归定义的 如费氏数列 2 问题解法按递归算法实现 如汉诺塔 3 数据的结构形式是按递归定义的 如二叉树 广义表等 遞迴資料 编辑主条目 递归数据类型 資料型別可以通過遞迴來進行定義 比如一個簡單的遞迴定義為自然數的定義 一個自然數或等於0 或等於另一個自然數加上1 Haskell中可以定義連結串列為 data ListOfStrings EmptyList Cons String ListOfStrings 這一定義相當於宣告 一個連結串列或是空串列 或是一個連結串列之前加上一個字串 可以看出所有連結串列都可以通過這一遞迴定義來達到 参考文献 编辑 Graham Ronald Donald Knuth Oren Patashnik Concrete Mathematics 1990 Chapter 1 Recurrent Problems 2011 12 22 原始内容存档于2020 11 06 英语 引文使用过时参数coauthors 帮助 Epp Susanna Discrete Mathematics with Applications 2nd 1995 427 英语 Wirth Niklaus Algorithms Data Structures Programs Prentice Hall 1976 126 英语 The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement In the same manner an infinite number of computations can be described by a finite recursive program even if this program contains no explicit repetitions 廖雪峰 递归函数 2018年8月18日11 19 21 原始内容存档于2018年9月24日 请检查 access date 中的日期值 帮助 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 原始内容存档于2018 03 09 英语 取自 https zh wikipedia org w index php title 递归 计算机科学 amp oldid 78599170, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。