递归与递推

递推

• 从1开始，向下求解，直到输出正确函数
• 用若干重复计算解决实际问题的方法
• 找规律构成递推式

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
	long arr[60] = {0};
	arr[1] = 1;
	arr[2] = 1;
	for (size_t i = 3;i <= 50; i++)
	{
		arr[i] = arr[i-1] + arr[i-2];
	}
	for (size_t i = 1; i <= 50; i++)
	{
		cout << i <<"	"<< arr[i] <<endl;
	}
	return 0;
}

• 又找到一道递推好题 洛谷P1044[栈]
• 上代码：

/*
    P1044递推解法
    注意到待入栈数n里的第k个数: 设其方案有f[k] (k > 0)
    则再设 k 前面的数的排列方式有 f[k-1] 种
    k 后面的数的排列方式有 f[n-k]种
    根据组合数原理: f[k] = f[k-1] * f[n-k]
    则有  f[n] = sum_{k = 0}^{n-1} f[k] 即 f[n] = f[0]f[n-1] + f[1]f[n-2] ...... + f[n-1]f[0]
    简单分析不难发现f[0] = 1 , f[1] = 1, f[2] = 2;
*/
 
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
int main()
{
    int n;
    long long f[20] = {1,1,2};
    cin >> n;
    //在这里 i 表示上文的 n ; j 表示上文的 k;
    //因为f[0] , f[1] , f[2] 均已明确 i 从 3 开始算;
    for (size_t i = 3; i <= n; i++)
    {
        for (size_t j = 1; j <= i; j++)
        {
            f[i] += f[j-1]*f[i-j];
        }
    }
    cout << f[n];
    return 0;
}

Important

主要在于对$N$里的任何一项$k$存在：$f(k)=f(k-1)\times f(n-k)$

$f(k)$表示第k项的情况:

则$f(N)={\sum }_{k=1}^{N-1}f(k)$

即：$f(n)=f(0)f(n-1)+f(1)f(n-2)......+f(n-1)f(0)$