递归(Recursion)
递归，常出现在声明式范式的语言中，用来实现过程迭代的语义；正如循环，常出现在命令式的语言中，用来实现数据迭代的语义。递归一般有两种：尾递归(tail recursion)与非尾部递归(non-tail recusion)，后者因为需要保存大量的临时变量，一般不被采用。下面使用不同的语言写一个常见的例子，求阶乘。1）使用Java求阶乘
// 非尾递归
public class Math {public static int fac(int n) {return n == 0 ? 1 : fac(n-1) * n; }public static void main(String[] args) {System.out.println(fac(5));}}
// 尾递归
public class Math {public static int fac(int result, int n) {return n == 0 ?result : fac(result*n, n-1);}public static int fac(int n) {return fac(1, n);}public static void main(String[] args) {System.out.println(fac(5));}}
2）使用C/C++求阶乘
// 非尾递归(C)
#include <stdio.h>#include <stdio.h>int fac(int n) { return n == 0 ? 1 : fac(n-1) * n;}int main(int argc, char*argv[]) { int result = fac(3); printf("The result is %d ", result); return 0;}
// 尾递归(C++)
#include <iostream> using namespace std; int fac(int result, int n) {return n == 0 ?result : fac(result*n, n-1);}int fac(int n) {return fac(1, n);}int main(int argc, char*argv[]) { int result = fac(3); cout << "The result is " << result; return 0;}
3）使用JavaScript求阶乘
// 非尾递归
// 这里提供了一些简单的谓词，以纯函数的风格表达递归
function div(a, b){return a/b; } function dec(x){return x - 1; } function equal(a, b){return a==b; } function fac(n){ return equal(n, 1) ? 1 : mul(n, fac(dec(n))); } document.write(fac(3));
// 尾递归（版本1）
// 在这里，通过JavaScript中arguments模拟重载不适用，
// 简单起见，也不再多写一个函数封装fac(result, n)来简化其参数个数。
// 因为后面有更简洁的表达方法，即采用闭包和匿名函数技术。
function fac(result, n) { return n == 0 ?result : fac(result*n, n-1);}document.write(fac(1, 3));
//尾递归（版本2）
// 这里采用闭包技术，但内部函数为具名函数，因为递归时需要呼叫函数的名字。
function fac(n) {return (function fac(result, n) {return n == 0 ?result : fac(result*n, n-1);})(1, n);}document.write(fac(5));
//尾递归（版本3）
// 这里采用闭包技术，内部函数之所以可以是匿名函数，是因为arguments.callee
// 即参数的被调用者的属性，可以引用匿名函数，在递归时可用来呼叫。
function fac(n) {return (function(result, n) {return n == 0 ?result : arguments.callee(result*n, n-1);})(1, n);}document.write(fac(5));
4）使用Erlang求阶乘
// non-tail recursion
-module(math).-export().fac(1) -> 1;fac(N) -> N * fac(N - 1)
// tail recursion
-module(math).-export().fac(N) -> fac(1, N).fac(Result, 1) -> Result;fac(Result, N) -> fac(N * Result, N - 1).
页:
[1]