2,443
个编辑
更改
跳到导航
跳到搜索
第3行：
第3行： − {{Short description|Use of functions that call themselves (on smaller inputs)}} − {{Use dmy dates|date=March 2020|cs1-dates=y}}+ − [[File:recursiveTree.JPG|thumb|300px|Tree created using the [[Logo (programming language)|Logo programming language]] and relying heavily on recursion. Each branch can be seen as a smaller version of a tree. 使用Logo 编程语言创建的树，主要使用递归方法。每一个分支都可以看作是一棵树的缩小版。]] − {{Programming paradigms}} − In [[computer science]], '''recursion''' is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.<ref>{{cite book − |author-last1 = Graham − |author-first1 = Ronald − |author-first2 = Donald |author-last2=Knuth |author-first3=Oren |author-last3=Patashnik − | title = Concrete Mathematics − | date= 1990 |isbn=0-201-55802-5 − | ref=harv − | chapter-url = http://www-cs-faculty.stanford.edu/~knuth/gkp.html − | chapter=1: Recurrent Problems − }}</ref> Such problems can generally be solved by [[Iteration#Computing|iteration]], but this needs to identify and index the smaller instances at programming time. Recursion solves such [[recursion|recursive problems]] by using [[function (computer science)|functions]] that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.<ref>{{cite book − |author-last = Epp − |author-first = Susanna − |title = Discrete Mathematics with Applications − |date = 1995 − |isbn = 978-0-53494446-9 − |edition = 2nd − |ref=harv − |page = [https://archive.org/details/discretemathema000epps/page/427 427] − |url = https://archive.org/details/discretemathema000epps/page/427 − }}</ref> − In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science. 第57行：
第33行： − {{quote|text=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.|author=[[Niklaus Wirth]]|source=''Algorithms + Data Structures = Programs'', 1976<ref>{{cite book |last = Wirth+ − |first = Niklaus − |author-link= Niklaus Wirth − |title = Algorithms + Data Structures = Programs − |publisher = [[Prentice-Hall]] − |isbn = 978-0-13022418-7 − |date = 1976 − |ref=harv − |page = [https://archive.org/details/algorithmsdatast00wirt/page/126 126] − |url = https://archive.org/details/algorithmsdatast00wirt/page/126 − }}</ref>}} − {{quote|text=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. 递归的强大力量很明显来源于其有限描述所定义出的无限对象。通过类似的递归定义，有限的递归程序也可以用来描述无限的计算，即使程序中没有包含明显的重复。|author=[[Niklaus Wirth]]|source=''Algorithms + Data Structures = Programs'', 1976<ref>{{cite book |last = Wirth − |first = Niklaus − |author-link= Niklaus Wirth − |title = Algorithms + Data Structures = Programs − |publisher = [[Prentice-Hall]] − |isbn = 978-0-13022418-7 − |date = 1976 − |ref=harv − |page = [https://archive.org/details/algorithmsdatast00wirt/page/126 126] − |url = https://archive.org/details/algorithmsdatast00wirt/page/126 − }}</ref>}} − -- [[用户:Qige96|Ricky]]：这里缺了一个quote模板。正确的显示应该是一段文摘引用：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 − − − Most computer [[programming language]]s support recursion by allowing a function to call itself from within its own code. Some [[functional programming]] languages (for instance, [[Clojure]])<ref>{{Cite web|title=Functional Programming {{!}} Clojure for the Brave and True|url=https://www.braveclojure.com/functional-programming/#Recursion_Instead_of_for_while|access-date=2020-10-21|website=www.braveclojure.com}}</ref> do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in [[computability theory]] that these recursive-only languages are [[turing completeness|Turing complete]]; this means that they are as powerful (they can be used to solve the same problems) as [[imperative language]]s based on control structures such as {{code|while}} and {{code|for}}. − − Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure) do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in computability theory that these recursive-only languages are Turing complete; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as {{code|while}} and {{code|for}} . − − Repeatedly calling a function from within itself may cause the [[call stack]] to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less [[algorithmic efficiency|efficient]], and, for large problems, it is fundamental to use optimization techniques such as [[tail call]] optimization.{{CN|date=November 2019}} − − Repeatedly calling a function from within itself may cause the call stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less efficient, and, for large problems, it is fundamental to use optimization techniques such as tail call optimization. − − {{toclimit|3}}
无编辑摘要
本词条由[[用户:Qige96|Ricky]]审校。
本词条由[[用户:Qige96|Ricky]]审校。
[[File:recursiveTree.JPG|thumb|300px|Tree created using the [[Logo (programming language)|Logo programming language]] and relying heavily on recursion. Each branch can be seen as a smaller version of a tree. 使用Logo 编程语言创建的树，主要使用递归方法。每一个分支都可以看作是一棵树的缩小版。]]
在计算机科学中，递归是一种解决问题的方法，其解决方案取决于同一问题的较小实例的解决方案。<ref>{{cite book
在计算机科学中，递归是一种解决问题的方法，其解决方案取决于同一问题的较小实例的解决方案。<ref>{{cite book
}}</ref>
}}</ref>
''递归的强大力量很明显来源于其有限描述所定义出的无限对象。通过类似的递归定义，有限的递归程序也可以用来描述无限的计算，即使程序中没有包含明显的重复。''
大多数计算机编程语言通过允许函数在其自己的代码中调用自己来支持递归。一些'''<font color="#ff8000"> 函数式编程语言 functional programming language</font>'''(例如Clojure<ref>{{Cite web|title=Functional Programming {{!}} Clojure for the Brave and True|url=https://www.braveclojure.com/functional-programming/#Recursion_Instead_of_for_while|access-date=2020-10-21|website=www.braveclojure.com}}</ref>)不定义任何循环结构，而只依赖递归来重复调用代码。在'''<font color="#ff8000">可计算性理论 computability theory</font>'''中证明了这些递归语言是'''<font color="#ff8000">图灵完备 Turing complete </font>'''这意味着它们与基于{{code|while}} 和{{code|for}}等控制结构的命令式语言一样强大(可以用于解决相同的问题)。
大多数计算机编程语言通过允许函数在其自己的代码中调用自己来支持递归。一些'''<font color="#ff8000"> 函数式编程语言 functional programming language</font>'''(例如Clojure<ref>{{Cite web|title=Functional Programming {{!}} Clojure for the Brave and True|url=https://www.braveclojure.com/functional-programming/#Recursion_Instead_of_for_while|access-date=2020-10-21|website=www.braveclojure.com}}</ref>)不定义任何循环结构，而只依赖递归来重复调用代码。在'''<font color="#ff8000">可计算性理论 computability theory</font>'''中证明了这些递归语言是'''<font color="#ff8000">图灵完备 Turing complete </font>'''这意味着它们与基于{{code|while}} 和{{code|for}}等控制结构的命令式语言一样强大(可以用于解决相同的问题)。
从自身内部反复调用一个函数可能会导致调用堆栈的大小等于所有参与调用的输入大小的总和。由此可见，对于可以通过迭代轻松解决的问题，递归的效率一般较低，而对于大型问题，使用诸如尾部调用优化之类的优化技术才是基本的（因为尾递归调用可以沿用原函数的栈空间，不会新增栈帧，可以避免栈溢出——译者注）。
从自身内部反复调用一个函数可能会导致调用堆栈的大小等于所有参与调用的输入大小的总和。由此可见，对于可以通过迭代轻松解决的问题，递归的效率一般较低，而对于大型问题，使用诸如尾部调用优化之类的优化技术才是基本的（因为尾递归调用可以沿用原函数的栈空间，不会新增栈帧，可以避免栈溢出——译者注）。