从递归开始的思考

by chainhelen

工程师眼中的递归

// 阶乘
function fact(num) {  
  if(0 == num || 1 == num) {
      return 1;
  }
  return num * fact(num - 1);
}

// 快排
void sort(int *a, int left, int right)  
{
    if(left >= right)
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
    while(i < j)                               
    {
        while(i < j && key <= a[j])
        {
            j--;
        } 
        a[i] = a[j];
        while(i < j && key >= a[i])
        {
            i++;
        }

        a[j] = a[i];
    }
    a[i] = key;
    sort(a, left, i - 1);
    sort(a, i + 1, right);
}

// express
next();

function next(err) {  
    if (err && err === 'route') {
    return done();
}

if (err && err === 'router') {  
    return done(err)
}

var layer = stack[idx++];  
if (!layer) {  
    return done(err);
}

if (layer.method && layer.method !== method) {  
    return next(err);
}

if (err) {  
    layer.handle_error(err, req, res, next);
} else {
    layer.handle_request(req, res, next);
}

程序调用自身的编程技巧称为递归（ recursion）

暂且定义为编程技巧，而不是算法

什么问题适合递归去解决

由来：动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法

分类：线性动规，区域动规，树形动规，背包动规四类（百度百科分类偏竞赛类）

针对问题：

​ 1.动态规划只能应用于有最优子结构的问题。如果问题的最优解所包含的子问题的解也是最优的。

​ 2.无后效性 即子问题的解一旦确定，就不再改变。

​ 3.子问题重叠性质（个人觉得非必要）

例子（取自wiki）

// 斐波那契数列 兔子
funcion fib(n) {  
    return (0 == n || 1 == n) ? 1 : fib(n - 1) + fib(n -2);
}

当n=5时，fib(5)的计算过程如下:

  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

=> 8次函数调用

1 1 2 3 5 8

$ F(n) = \frac{\sqrt5}{5}[{(\frac{1+\sqrt5}{2})}^n - {(\frac{1-\sqrt5}{2})}^n]$

可以看到指数级复杂度

使用动态规划，计算fib(n)会有两个子问题fib(n - 1)，fib(n - 2)，实际计算fib(n - 1)的时候还会包含fib(n - 2)这个子问题，所以在fib(n - 2)计算完毕后使用表记录下来 

let mp = {};  
function fib(n) {  
    if (0 == n || 1 == n) {
        return 1;
    }
    return (mp[n - 1] ? mp[n - 1] : (mp[n - 1] = fib(n - 1))) + 
    (mp[n - 2] ? mp[n - 2] : (mp[n - 2] = fib(n - 2)));
}

非递归版本

function fib(n) {  
   let a = 0;
   let b = 1;
   while(n--) {
       a += b; 
       a^= b;
       b^= a;
       a^= b;
   }
   return a;
}

尾递归

function fib(n, r1, r2) {  
   return 0 == n ? r1 : fib(n - 1, r2, r1 + r2);
}

我的理解是不依赖栈保存状态

定义数据

一个简单的递归定义为自然数的定义：“一个自然数或等于0，或等于另一个自然数加上1”

bnf范式中的例子，chlang 抽象语法树节点，取函数形参参数形成

//parameter_list
//    : NULL
//    | IDENTIFIER
//    | IDENTIFIER COMMA parameter_list

Y组合子

不动点

通常的理解：函数中映射到自身一个点，可以理解为 \(f(x) = x\)的点

例如在 实数 映射 实数 的函数 \(f(x) = x^2 -x + 1\)，其中\(x = 1\)是\(f\)的一个不动点

例如利用不动点方式解数列通项公式(高中数学) ，本质上是解一个其次方程组

​ \(a_{n + 1} - 2 * a_{n} + 1 = 0 \)

​ \(x^2 - 2 * x + 1 = 0\)

​ \((x - 1)^2 = 0\)

\(x = 1\) 为不动点

则\( (a_{n + 1} - 1) = 2 (a_n - 1) \) 求解

冒泡排序 : 4 1 2 3​ => 1 2 3 4

编译原理 : 子集构造法

\(\lambda\) 演算

\(\lambda\) 演算的共同主题是找到\(\lambda\)表达式的不动点

每个\(\lambda\)表达式都有一个不动点，而Fixed-point combinator 或不动点算子是计算其他函数的一个不动点的高阶函数

输入是一个表达式(函数、变量等)，并输出该表达式的不动点

例子来源wiki :

表达式"加2" ： \( \lambda x.x + 2 \)

表达式"函数 f 传入3" ： \(\lambda f.f \ 3\)

\(3 + 2 => (\lambda x.x + 2)\ 3 => (\lambda y. y\ 3)(\lambda x.x + 2)\)

为什么要找到\(\lambda\)表达式的不动点，为了实现递归

\(\lambda\)演算的系统中并不存在函数名，那么就会存在如何实现递归的问题

1.首先通常阶乘写法

\(fact = \lambda x.if(x > 0) then (x * (fact(x - 1)))else(1) \)

2.期望不需要fact名字，fact是 free variable

首先按照上面的方式将fact作为变量，定义一个新的函数

\(fact^{'} = \lambda f. \lambda x.if(x>0)then(x * (f(x - 1)))else(1) \)

那么 \(fact = fact^{'} fact\)

这个表达式左右两边还是有关联\( fact \) 继续处理，假设存在这样的\( Y = \lambda f. f(Y f)\) 利用这个\( Y \)处理下面式子

\( fact = Y fact^{'} = fact^{'} ( Y fact^{'}) = fact^{'} fact\)

然后科学家们找到了这样的东西

\(Y = \lambda f.(\lambda x. f(x \ x))(\lambda x.f(x \ x))\)

\( \begin{equation}\begin{split} Y g&=(\lambda x.g (x\ x))(\lambda x.g (x\ x))\\

&=(\lambda y.g (y\ y))(\lambda x.g (x\ x)) \ \alpha 变换\\ & = g\ ((\lambda x.g (x\ x))(\lambda x.g (x\ x))) \ \beta 规约\\ & = g\ (Y g) \end{split}\end{equation} \)

var y_combinator = function(fn) {  
    return (function(u) {
        return u(u);
    })(function(x) {
        return fn(function() {
            return x(x).apply(null, arguments);
        });
    });
};

y_combinator(function(fact) {  
    return function(n) {
        return n <= 1? 1: n * fact(n - 1);
    };
})(10);

递归可枚举

在可计算性理论中，一个自然数的子集被称为递归的、可计算的或具有可判定性

递归可枚举集合: 可数集合S被称为递归可枚举的, 如果存在生成S的元素的算法. 等价定义:可数集合S被称为递归可枚举的, 如果有一个图灵机, 在给定S的一个元素作为输入的时候总是停机, 并在给定的输入不属于S的时候永不停机.

递归集合: 可数集合S被称为递归的, 如果存在能够在有限步骤内判定任意给定元素是否属于S的算法.

对于一个判定问题，如果能够编出一个程序，以域中任意元素作为输入，执行该程序就能给出相应的个别问题的答案，就称该判定问题为可判定的。例如，“任意正整数是不是素数”这个问题就是可判定的。对于集合A，域中任意元素是否属于它的问题称为集合 A对应的判定问题。集合是递归集的充分必要条件为对应的判定问题是可判定的。因此，全体素数的集合是递归集。

对于一个判定问题，如果能够编出一个程序P，以域中任意元素作为输入，当相应的个别问题的解答是肯定的时候，P的执行将终止并输出“是”，否则P的执行不终止，就称该判定问题为半可判定的。可判定的问题总是半可判定的。集合是递归可枚举集的充分必要条件为对应的判定问题是半可判定的