不忘初心

少年,专心练剑吧

谈谈尾递归和矩阵快速幂

发表于 更新于 分类于

尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。例如：return f(n-1);而 return n + f(n-1) ;则不是。

以求阶乘为例，一般写法如下,如果这个函数调用的深度太深，很容易会有爆栈的危险。

1
2
3
4
5
6
int factorial(int n) {
    if(n == 1) {
        return 1;
    }
    return n * factorial(n-1);
}

尾递归写法如下，求10的阶乘为factorial(10, 1)，尾递归把返回结果放到了调用的参数里，因此理论上可以先把之前的栈释放掉。

1
2
3
4
5
6
int factorial(int n, int m) {
    if(n == 1) {
        return 1 * m;
    }
    return factorial2(n-1, m*n);
}

参考文章：
说说尾递归 - twoon

矩阵快速幂

快速幂：假设有一个整数 x， 如果我们要求出 x^n （即为 x 的 n 次方）的值，最容易想到的办法就是循环相乘（这里不考虑整数溢出的情况下），于是我们很容易就可以写出下面的代码：

1
2
3
4
int res = 1;
for (int i = 0; i < n; i++) {
    res *= x;
}

当我们计算2^9时，可分解为：

原先需要计算8次，现在只需要计算4次（2*2, 4*4, 16*16, 2*256)

当我们计算2^10时，可分解为：

以下为快速幂算法，其时间复杂度为 O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int QuickPow(int x,int N)
{
    int res = x;
    int ans = 1;
    while(N)
    {
        if(N&1)
        {
            ans = ans * res;
        }
        res = res*res;
        N = N>>1;
    }
    return ans;
}

矩阵快速幂是用于快速求出一个矩阵的 n 次方的方法。常规运算只要把快速幂中的底数换成矩阵即可。
具体应用以斐波那契数列为例：

f(1) = 1 f(2) = 1 f(n) = f(n-1)+f(n-2)

用矩阵表示为：

易得：

根据矩阵乘法：

所以求斐波那契数列的第n项(n>=3)：

即：

然后就可以使用矩阵快速幂来计算了。