2,443
个编辑
更改
跳到导航
跳到搜索
第1,024行：
第1,024行： − Most [[programming language]]s in use today allow the direct specification of recursive functions and procedures. When such a function is called, the program's [[runtime environment]] keeps track of the various [[Instance (computer science)|instance]]s of the function (often using a [[call stack]], although other methods may be used). Every recursive function can be transformed into an iterative function by replacing recursive calls with [[Control flow|iterative control constructs]] and simulating the call stack with a [[stack (data structure)|stack explicitly managed]] by the program.<ref>{{citation|title=Python Algorithms: Mastering Basic Algorithms in the Python Language|first=Magnus Lie|last=Hetland|publisher=Apress|date=2010|isbn=9781430232384|page=79|url=https://books.google.com/books?id=4cytGpIPYsAC&pg=PA79}}.</ref><ref>{{citation|title=Data Structures and Algorithms in C++|first=Adam|last=Drozdek|edition=4th|publisher=Cengage Learning|date=2012|isbn=9781285415017|page=197|url=https://books.google.com/books?id=PRgLAAAAQBAJ&pg=PA197}}.</ref> − − Conversely, all iterative functions and procedures that can be evaluated by a computer (see [[Turing completeness]]) can be expressed in terms of recursive functions; iterative control constructs such as [[while loop]]s and [[for loop]]s are routinely rewritten in recursive form in [[functional language]]s.<ref>{{cite web|url=http://www.ccs.neu.edu/home/shivers/papers/loop.pdf |title=The Anatomy of a Loop - A story of scope and control |publisher=Georgia Institute of Technology |first=Olin |last=Shivers |accessdate=2012-09-03}}</ref><ref>{{cite web|author=Lambda the Ultimate |url=http://lambda-the-ultimate.org/node/1014 |title=The Anatomy of a Loop |publisher=Lambda the Ultimate |accessdate=2012-09-03}}</ref> However, in practice this rewriting depends on [[tail call elimination]], which is not a feature of all languages. [[C (programming language)|C]], [[Java (programming language)|Java]], and [[Python (programming language)|Python]] are notable mainstream languages in which all function calls, including [[tail call]]s, may cause stack allocation that would not occur with the use of looping constructs; in these languages, a working iterative program rewritten in recursive form may [[stack overflow|overflow the call stack]], although tail call elimination may be a feature that is not covered by a language's specification, and different implementations of the same language may differ in tail call elimination capabilities.
→表达能力
===表达能力===
===表达能力===
今天使用的大多数编程语言都允许直接编写递归函数和程序。当这样的函数被调用时，程序的运行时环境会跟踪该函数的各种实例（通常使用调用栈，也可能会使用其他方法）。每一个递归函数都可以被转换成迭代函数，用迭代控制构造代替递归调用，并用程序显式管理的自己的栈来模拟系统调用栈。<ref>{{citation|title=Python Algorithms: Mastering Basic Algorithms in the Python Language|first=Magnus Lie|last=Hetland|publisher=Apress|date=2010|isbn=9781430232384|page=79|url=https://books.google.com/books?id=4cytGpIPYsAC&pg=PA79}}.</ref><ref>{{citation|title=Data Structures and Algorithms in C++|first=Adam|last=Drozdek|edition=4th|publisher=Cengage Learning|date=2012|isbn=9781285415017|page=197|url=https://books.google.com/books?id=PRgLAAAAQBAJ&pg=PA197}}.</ref>
今天使用的大多数编程语言都允许直接编写递归函数和程序。当这样的函数被调用时，程序的运行时环境会跟踪该函数的各种实例（通常使用调用栈，也可能会使用其他方法）。每一个递归函数都可以被转换成迭代函数，用迭代控制构造代替递归调用，并用程序显式管理的自己的栈来模拟系统调用栈。<ref>{{citation|title=Python Algorithms: Mastering Basic Algorithms in the Python Language|first=Magnus Lie|last=Hetland|publisher=Apress|date=2010|isbn=9781430232384|page=79|url=https://books.google.com/books?id=4cytGpIPYsAC&pg=PA79}}.</ref><ref>{{citation|title=Data Structures and Algorithms in C++|first=Adam|last=Drozdek|edition=4th|publisher=Cengage Learning|date=2012|isbn=9781285415017|page=197|url=https://books.google.com/books?id=PRgLAAAAQBAJ&pg=PA197}}.</ref>
相应得，所有可以被计算机求解的迭代函数和程序(见图灵完备性)都可以用递归函数来表达；在函数式语言中，诸如while循环和for循环等迭代控制构造经常以递归形式重写<ref>{{cite web|url=http://www.ccs.neu.edu/home/shivers/papers/loop.pdf |title=The Anatomy of a Loop - A story of scope and control |publisher=Georgia Institute of Technology |first=Olin |last=Shivers |accessdate=2012-09-03}}</ref><ref>{{cite web|author=Lambda the Ultimate |url=http://lambda-the-ultimate.org/node/1014 |title=The Anatomy of a Loop |publisher=Lambda the Ultimate |accessdate=2012-09-03}}</ref>。然而，在实践中，这种重写依赖于尾部调用的消除，而这并不是所有语言的特征。C、Java和Python是值得注意的主流语言，在这些语言中，所有的函数调用（包括尾部调用）都可能会引起栈分配，而使用循环结构则不会出现这种情况；在这些语言中，以递归形式重写的迭代程序可能会造成调用栈溢出，不过尾部调用消除可能是语言规范中没有涉及的功能，同一语言的不同实现在尾部调用消除能力上可能会有所不同。
相应得，所有可以被计算机求解的迭代函数和程序(见图灵完备性)都可以用递归函数来表达；在函数式语言中，诸如while循环和for循环等迭代控制构造经常以递归形式重写<ref>{{cite web|url=http://www.ccs.neu.edu/home/shivers/papers/loop.pdf |title=The Anatomy of a Loop - A story of scope and control |publisher=Georgia Institute of Technology |first=Olin |last=Shivers |accessdate=2012-09-03}}</ref><ref>{{cite web|author=Lambda the Ultimate |url=http://lambda-the-ultimate.org/node/1014 |title=The Anatomy of a Loop |publisher=Lambda the Ultimate |accessdate=2012-09-03}}</ref>。然而，在实践中，这种重写依赖于尾部调用的消除，而这并不是所有语言的特征。C、Java和Python是值得注意的主流语言，在这些语言中，所有的函数调用（包括尾部调用）都可能会引起栈分配，而使用循环结构则不会出现这种情况；在这些语言中，以递归形式重写的迭代程序可能会造成调用栈溢出，不过尾部调用消除可能是语言规范中没有涉及的功能，同一语言的不同实现在尾部调用消除能力上可能会有所不同。