笨人小白的温故知新——递归（4）

1202：Pell数列

其实本来是一段很简单的代码，但是这个题带给我的收获很大，所以我决定来做一个自己的反思回顾。

来讲一下我做这道题遇到的问题（主要是解决运行超时的问题）：

1）我一开始并没有用记忆化，导致运行超时。

2）我用了一个记忆化（但是是错的）

long long pell(int k){ if(！pell(k)) return ; }

现在，我已经知道了我的错因：!pell(k)试图判断返回值是否为 0，但pell(k)本身又会无限递归，永远无法执行到后续逻辑；

3）然后我做了如下改动：

const int MOD = 32767 , N = 1e6+10; long long a[N] ; long long pell(int k){ if(a[k] != 0) return a[k] ; if(k == 1) return 1 ; if(k == 2) return 2 ; a[k] = (2*pell(k-1) + pell(k-2))%MOD ; return a[k] ; }

这样，就获得了一个AC代码：

#include <iostream> #include <stdio.h> using namespace std ; const int MOD = 32767 , N = 1e6+10; long long a[N] ; long long pell(int k){ if(a[k] != 0) return a[k] ; if(k == 1) return 1 ; if(k == 2) return 2 ; a[k] = (2*pell(k-1) + pell(k-2))%MOD ; return a[k] ; } int main() { int n , s ; scanf("%d" , &n) ; while(n--){ scanf("%d" , &s) ; printf("%lld\n" , pell(s)) ; } return 0; }

你以为这就结束了？NO~~~ 好奇的我，又换了一种：

a[k] = 2*pell(k-1)%MOD + pell(k-2)%MOD ;

但是却运行超时了。why？

笨笨的我问了豆包，豆包说：

“取模是「相对耗时」的操作

取模（%）本质是除法 + 求余，属于 CPU 的复杂指令（比加法 / 乘法慢得多）。前者只执行 1 次取模，后者执行 2 次，仅这一步就会产生「指令数翻倍」的开销 —— 尤其是在循环 / 递归的高频调用场景下（比如计算 pell (1e5)），两次取模的累计耗时会被放大，最终体现为「后者更慢」。”

今天也回顾了好几道题，但是都比较简单，所以没有写到我的博客里。（嘻嘻