2,443
个编辑
更改
跳到导航
跳到搜索
第978行：
第978行： − − Recursion and [[iteration]] are equally expressive: recursion can be replaced by iteration with an explicit [[call stack]], while iteration can be replaced with [[tail call|tail recursion]]. Which approach is preferable depends on the problem under consideration and the language used. In [[imperative programming]], iteration is preferred, particularly for simple recursion, as it avoids the overhead of function calls and call stack management, but recursion is generally used for multiple recursion. By contrast, in [[functional programming|functional languages]] recursion is preferred, with tail recursion optimization leading to little overhead. Implementing an algorithm using iteration may not be easily achievable. − − Compare the templates to compute x<sub>n</sub> defined by x<sub>n</sub> = f(n, x<sub>n-1</sub>) from x<sub>base</sub>: 第1,003行：
第999行： − For imperative language the overhead is to define the function, for functional language the overhead is to define the accumulator variable x. − For example, a [[factorial]] function may be implemented iteratively in [[C (programming language)|C]] by assigning to an loop index variable and accumulator variable, rather than by passing arguments and returning values by recursion:
→递归 VS 迭代
==递归 VS 迭代==
==递归 VS 迭代==
递归和迭代的表达能力是一样的：递归可以用显式调用栈的迭代代替，而迭代可以用尾递归代替。哪种方法更合适，取决于所考虑的问题和所使用的语言。在命令式编程中，迭代是首选，特别是对于简单递归，因为它避免了函数调用的开销和调用栈管理，但在多重递归问题时通常还是要用到递归方法。相比之下，在函数式语言中，递归是首选的，因为尾递归优化只带来很少的开销。使用迭代实现算法可能不容易实现。
递归和迭代的表达能力是一样的：递归可以用显式调用栈的迭代代替，而迭代可以用尾递归代替。哪种方法更合适，取决于所考虑的问题和所使用的语言。在命令式编程中，迭代是首选，特别是对于简单递归，因为它避免了函数调用的开销和调用栈管理，但在多重递归问题时通常还是要用到递归方法。相比之下，在函数式语言中，递归是首选的，因为尾递归优化只带来很少的开销。使用迭代实现算法可能不容易实现。
比较x<sub>base</sub>中，由x<sub>n</sub> = f(n, x<sub>n-1</sub>)定义的计算x<sub>n</sub>的模板:
比较x<sub>base</sub>中，由x<sub>n</sub> = f(n, x<sub>n-1</sub>)定义的计算x<sub>n</sub>的模板:
|}
|}
对于命令式语言，开销是定义函数，对于函数式语言，开销是定义累加器变量x。
对于命令式语言，开销是定义函数，对于函数式语言，开销是定义累加器变量x。
例如，在C语言中，一个阶乘函数可以通过分配给循环索引变量和累加器变量来迭代实现，而不是通过递归传递参数和返回值。
例如，在C语言中，一个阶乘函数可以通过分配给循环索引变量和累加器变量来迭代实现，而不是通过递归传递参数和返回值。