递归(Recursion)

mindfocus

递归，常出现在声明式范式的语言中，用来实现过程迭代的语义；正如循环，常出现在命令式的语言中，用来实现数据迭代的语义。递归一般有两种：尾递归(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]).fac(1) -> 1;fac(N) -> N * fac(N - 1)

// tail recursion
-module(math).-export([fac/1]).fac(N) -> fac(1, N).fac(Result, 1) -> Result;fac(Result, N) -> fac(N * Result, N - 1).