数据结构算法每日一练（二）Lagureer多项式
1、N次Laguerre多项式$P_n(x)$的递归定义是：
$P_0(x)=1$
$P_1(x)=1-x$
$P_n(x) = (2n-1-x) P_{n-1}(x) - (n-1)^2 P_{n-2}(x) (n>1)$(1)请按照上面的定义用递归的方式求n次Lagureer 多项式在x处的值: double laguerre (double x，int n);
(2)给出此递归函数的时间复杂度。
（1）
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
double laguerre (double x, int n){
if(n == 0) {
return 1;
}else if(n == 1) {
return 1 - x;
}else {
return (2*n - 1 - x) * laguerre(x, n - 1) - (n - 1) * (n - 1) * laguerre(x, n - 2);
}
}
int main() {
double x;
int n ;
cin >> x >> n;
double res = laguerre(x, n);
cout << res << endl;
return 0;
}（2）时间复杂度为递归调用$O(2^n)$
详细分析请参照上篇-斐波那契数列
