370
个编辑
更改
无编辑摘要
{{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
{{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
|first = Niklaus
|author-link= Niklaus Wirth
|author-link= Niklaus Wirth
* 与此相反，生成递归是指没有这样明显的循环变体，终止取决于一个函数，如 "近似误差"，而这个函数不一定会降为零，因此，如果不作进一步的分析，就不能保证终止。
* 与此相反，生成递归是指没有这样明显的循环变体，终止取决于一个函数，如 "近似误差"，而这个函数不一定会降为零，因此，如果不作进一步的分析，就不能保证终止。
==Recursive programs==
==递归程序==
===递归过程===
====阶乘====
A classic example of a recursive procedure is the function used to calculate the [[factorial]] of a [[natural number]]:
A classic example of a recursive procedure is the function used to calculate the [[factorial]] of a [[natural number]]:
\end{cases}
\end{cases}
</math>
</math>
{| class="wikitable"
{| class="wikitable"
The function can also be written as a [[recurrence relation]]:
The function can also be written as a [[recurrence relation]]:
该函数也可以写成递归关系式：
:<math>b_n = nb_{n-1}</math>
:<math>b_n = nb_{n-1}</math>
:<math>b_0 = 1</math>
:<math>b_0 = 1</math>
This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:
This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:
This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:
This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:
这种对递归关系的求值展示了在执行上述伪代码时将进行的计算。
{| class="wikitable"
{| class="wikitable"
The imperative code above is equivalent to this mathematical definition using an accumulator variable {{math|<var>t</var>}}'':
The imperative code above is equivalent to this mathematical definition using an accumulator variable {{math|<var>t</var>}}'':
上面的命令式代码相当于这个使用累加器变量{{math|<var>t</var>}的数学定义:
:<math>
:<math>
The definition above translates straightforwardly to [[functional programming language]]s such as [[Scheme (programming language)|Scheme]]; this is an example of iteration implemented recursively.
The definition above translates straightforwardly to [[functional programming language]]s such as [[Scheme (programming language)|Scheme]]; this is an example of iteration implemented recursively.
上面的定义可以直接翻译成函数式编程语言，比如Scheme；这就是一个递归实现迭代的例子。
====最大公约数====
The [[Euclidean algorithm]], which computes the [[greatest common divisor]] of two integers, can be written recursively.
The [[Euclidean algorithm]], which computes the [[greatest common divisor]] of two integers, can be written recursively.