递归和非递归

能采用递归解决的问题通常具有以下特征

规模为 \(n\) 的问题可以被分解为一些规模较小的问题，然后从这些小问题的解可以方便地构造出大问题的解而这些小问题可以同样的方式继续分解成规模更小的问题，当问题分解到足够小的时候，能直接得到解

递归树、剪枝、记忆化不再赘述

分治思想

把一个规模比较大的问题分解为一个或若干规模比较小的问题，分别对这些较小的问题求解，再综合它们的结果，从而得到原问题的解。这些比较小的问题的求解方法与原来问题的求解方法一样

分解
解决
合并

时间复杂度分析

设一个分治算法将规模 \(n\) 问题分解为 \(a\) 个规模 \(\frac{n}{b}\) 的子问题，合并子问题需要的计算量为 \(f(n)\)

则 \[T(n)=\begin{cases}O(n^{\log _b(a) })& n^{loag_b(a)} > f(n) \\\\ O(f(n)\log _b(n)) & n^{loag_b(a)}=f(n) \\\\ O(f(n)) & n^{loag_b(a)} <f(n) \end{cases} \]

点击查看证明

容易知道 \[T(n)=\begin{cases}O(1)& n=1 \\\\ aT(\frac{n}{b})+f(n) & n > 1 \end{cases}\]

\(n>1\) 时有 \(T(n)=aT(\frac{n}{b})+f(n)\)

当 \(n=b^m\) 时，\(T(b^m)=aT(b^{m-1})+f(b^{m})\)

则 \(\frac{T(b^m)}{a^m}=\frac{T(b^{m-1})}{a^{m-1}}+\frac{f(b^{m})}{a^m}\)

记 \(R(m)=\frac{T(b^m)}{a^m}\) 则 \(R(m)=R(m-1)+\frac{f(b^{m})}{a^m}\)

则 \(R(m)=\frac{T(b^m)}{a^m}=\sum_{i=0}^m\frac{f(b^{i})}{a^i}\)

则 \(T(b^m)=a^m\sum_{i=0}^m\frac{f(b^{i})}{a^i}\)

由于 \(n=b^m\) 则 \(m=\log _b(n)\)

根据对数性质 \(a^m=n^{\log _b(a)}\)

当 \(n^{\log_a(b)} > f(n)\) 时 \(\sum_{i=0}^m\frac{f(b^{i})}{a^i}=O(1)\)，\(T(n)=O(n^{\log _b(a)})\)

当 \(n^{\log_a(b)} = f(n)\) 时 \(\sum_{i=0}^m\frac{f(b^{i})}{a^i}=m\)，\(T(n)=mf(n)=f(n)\log_b(a)\)

当 \(n^{\log_a(b)} < f(n)\) 时，\(T(n)=\sum_{i=0}^mf(i)=O(f(n))\)

Strassen 矩阵乘法

算法思想

将两个 \(n\times n\) 矩阵 \(A\) 和 \(B\) 按中点分块（假设 \(n\) 为偶数）： \[ A=\begin{pmatrix}A_{11} & A_{12}\\\\ A_{21} & A_{22}\end{pmatrix},\qquad B=\begin{pmatrix}B_{11} & B_{12}\\\\ B_{21} & B_{22}\end{pmatrix}, \] 每个子块为 \(\frac{n}{2}\times\frac{n}{2}\)。

传统的分块乘法需要 8 次子矩阵乘法： \[ \begin{aligned} C_{11} &= A_{11}B_{11} + A_{12}B_{21},\\\\ C_{12} &= A_{11}B_{12} + A_{12}B_{22},\\\\ C_{21} &= A_{21}B_{11} + A_{22}B_{21},\\\\ C_{22} &= A_{21}B_{12} + A_{22}B_{22}. \end{aligned} \]

Strassen 的关键是构造 7 个“辅助乘积” \[M_1,\dots,M_7\]（每个都是 \(\frac{n}{2}\times\frac{n}{2}\) 矩阵的乘积），然后用这些乘积组合出 \(C_{ij}\)。一种常见的构造为：

\[ \begin{aligned} M_1 &= (A_{11} + A_{22})\,(B_{11} + B_{22}),\\\\ M_2 &= (A_{21} + A_{22})\,B_{11},\\\\ M_3 &= A_{11}\,(B_{12} - B_{22}),\\\\ M_4 &= A_{22}\,(B_{21} - B_{11}),\\\\ M_5 &= (A_{11} + A_{12})\,B_{22},\\\\ M_6 &= (A_{21} - A_{11})\,(B_{11} + B_{12}),\\\\ M_7 &= (A_{12} - A_{22})\,(B_{21} + B_{22}). \end{aligned} \]

然后恢复结果子块为：

\[ \begin{aligned} C_{11} &= M_1 + M_4 - M_5 + M_7,\\\\ C_{12} &= M_3 + M_5,\\\\ C_{21} &= M_2 + M_4,\\\\ C_{22} &= M_1 - M_2 + M_3 + M_6. \end{aligned} \]

这样每一层递归只需要 \(7\) 次子矩阵乘法，另外外加若干次矩阵加减（加减的时间量级为 \(O(n^2)\)）

复杂度分析

设 Strassen 在大小 \(n\) 的矩阵上耗时为 \(T(n)\)。每次将问题分为 7 个子问题（规模为 \(\frac{n}{2}\)）并进行矩阵加减（合并开销为 \(O(n^2)\)），

应用上面的定理：

令 \[a=7, b=2, f(n)=\Theta(n^2)\]

因此有递推式： \[ T(n) = \begin{cases}\Theta(1), & n=1,\\\\7\,T\left(\frac{n}{2}\right) + \Theta(n^2), & n>1.\end{cases} \]

目前最新进展已经到 \(O(n^{2.373})\)

Matrix multiplication - Wikipedia

递归与非递归

递归缺点：

有栈空间溢出的风险
堆栈空间以及函数调用造成较大的时间与空间开销

但是这不代表代码执行效率低，相反，有时递归比非递归快，两者实际是相当的

Hanoi 塔的非递归实现

写出 Hanoi(n,A,B,C) 的递归树，进行树的先序遍历，仿照系统栈的方式实现递归

非递归实现1：与递归树等价的非递归实现

struct node{
	int n, tag;
	char a, b, c;
	node(){}
	node (int _n , char _a , char _b , char _c , int _tag = 0){
		n = _n, a = _a, b = _b, c = _c, tag = _tag;
    }
};
void set_value(int& n, char& a, char& b, char& c, int nn , char aa , char bb , char cc){
    n = nn, a = aa, b = bb, c = cc;
}

void move_disk (char from, char to){
    cout << "Move top disk from "<< from << " to "<< to << endl;
}


void hanoi(int N, char a, char b, char c){
    stack<node> S;
    bool done = false;
    while(!done){
        while(n > 1){
            S.push(node(n, a,b, c));
            set_value(N, a,b, c, N - 1, a, c, b);
        }
        move_dist(a, c);
        if(!s.empty()){
            node s = S.top();
            S.pop();
            set_value(N, a, b, c, s.n, s.a, s.b, s.c);
			move_disk(a, c);
            set_value(N, a, b, c, n - 1, b, a, c);
        }
        else done = true;
    }
}

其他的实现方式

和递归树不等价

void hanoi2(int N, char a, char b,char c){
    stack<node> S;
    S.push(node(N, a,b, c));
    while(!S.empty()){
        node s = S.top(); S.pop();
        N = s.n, a = s.a, b = s.b, c = s.c;
        if(N == 1){
			move_disk(a, c);
		}else{
			S.push(node(N-l,b, a, c));
			S.push(node(l, a,b,c));
			S.push(node(N-l, a,c, b));
        }
    }
}

定义三根柱子为 \(A, B, C\)，用数组 \(dict[0\ldots 2]\) 表示： \[ dict[0] = A, \quad dict[1] = B, \quad dict[2] = C \]

第 \(i\) 步移动的 起点柱子 用函数 \(F(i)\) 表示，第 \(i\) 步移动的 终点柱子 用函数 \(G(i)\) 表示

起点柱子函数 \[ F(i) = (i \\& (i-1)) \bmod 3 \]

\(i\) 的二进制表示与 \((i-1)\) 的按位与，可以得到当前移动的盘子编号对应的柱子位置的模式

终点柱子函数 \[ G(i) = ((i | (i-1)) + 1) \bmod 3 \]

\((i | (i-1)) + 1\) 经过二进制运算可以得到该盘子移动后的目标柱子编号

汉诺塔问题的盘子移动顺序存在规律：
- 第 \(k\) 个盘子每隔 \(2^{k}\) 步移动一次；
- 最小盘子移动规律最简单，次小盘子次之。
利用位运算：
- \(i \\& (i-1)\) 可以计算第 \(i\) 步移动的盘子编号；
- \(i | (i-1)\) 可以确定该盘子目标位置的循环规律。
最终公式：

\[ \text{Move at step } i: \quad \text{from } dict[F(i)] \text{ to } dict[G(i)], \quad i=1,2,\dots,2^N-1 \]

inline int f(int x){return(x&x - 1)%3;}
inline int g(int x){freturn((x|x - 1） + 1)%3;}

void hanoi3(int N, char a, char b, char c){
	int n = (1<<N)- 1;
	char dict[3];
	dict[0] = a,dict[1] = b, dict[3]= c;
	for(int i = 1; i <= n; i++){
		cout << dict[F(i)］<<" "<< dict[G(i)]<< endl;
    }
}

_hanoi:                         # void hanoi(int N, char a, char b, char c)
    push    rbp
    mov     rbp, rsp
    sub     rsp, 32
    mov     DWORD PTR [rbp-20], edi      # N
    mov     BYTE PTR [rbp-21], sil       # a
    mov     BYTE PTR [rbp-22], dl        # b
    mov     BYTE PTR [rbp-23], cl        # c

    cmp     DWORD PTR [rbp-20], 1
    jne     .Lrecursion

    movzx   edx, BYTE PTR [rbp-23]       # to
    movzx   eax, BYTE PTR [rbp-21]       # from
    mov     esi, eax
    mov     edi, edx
    call    _move_disk
    jmp     .Lreturn

.Lrecursion:
    mov     eax, DWORD PTR [rbp-20]
    lea     edi, [rax-1]                 # n-1
    movzx   esi, BYTE PTR [rbp-21]       # a
    movzx   edx, BYTE PTR [rbp-23]       # c
    movzx   ecx, BYTE PTR [rbp-22]       # b
    call    _hanoi                       # hanoi(n-1, a, c, b)

    movzx   edx, BYTE PTR [rbp-23]
    movzx   eax, BYTE PTR [rbp-21]
    mov     esi, eax
    mov     edi, edx
    call    _move_disk                   # move_disk(a, c)

    mov     eax, DWORD PTR [rbp-20]
    lea     edi, [rax-1]
    movzx   esi, BYTE PTR [rbp-22]
    movzx   edx, BYTE PTR [rbp-21]
    movzx   ecx, BYTE PTR [rbp-23]
    call    _hanoi                       # hanoi(n-1, b, a, c)

.Lreturn:
    leave
    ret

void hanoi4(int N, char a, char b, char c) {
    stack<node> S;
A: 
    if (N == 1) {
        move_disk(a, c);
        goto B; 
    } else {
        S.push(node(N, a, b, c, 1));
        set_value(N, a, b, c, N - 1, a, c, b);
        goto A;
    }

B:
    if (!S.empty()) {
        node s = S.top(); S.pop();
        set_value(N, a, b, c, s.n, s.a, s.b, s.c);
        switch (s.tag) {
            case 1: {
                move_disk(a, c);
                S.push(node(N, a, b, c, 2));
                set_value(N, a, b, c, N - 1, b, a, c);
                goto A;
            }
            case 2: {
                goto B;
            }
        }
    }
}

递归消除

尾递归

递归调用处于递归过程的最后一条语句的情况

int f(int n){
    if(n == 1) return n;
    else return n*f(n-1)
}

改为

int f(int n){
    int f = 1;
    for(int i = 2; i <= n; ++i) f = n*f;
    return f;
}

线性递归

线性递归函数的最后一步不是递归操作，而是其他操作

void example(int n){
    S1(n);
    if(Eval(n)){
        example(n-1);
        S2(n);
    }
    else S3(n);
}

根据系统栈的调用，改为

void example(int n){
    int k = n+1;
    do{
        k--;
        S1(k);
    } while(Eval(k));
    S3(k);
    while(k < n){
        k++;
        S2(k);
    }
}

(´-ω-｀)