递归算法概述：
递归算法是一种在函数或方法中调用自身来解决问题的算法。它是一种强大的技术，可以用来解决各种复杂的问题，特别是那些可以分解为更小、更相似子问题的问题。递归算法通常涉及两个主要部分：基本情况（base case）和递归步骤（recursive step）。
基本概念
1. 基本情况（Base Case）：这是递归调用结束的条件。在基本情况下，问题被解决而不再进行递归调用。
2. 递归步骤（Recursive Step）：这是算法分解问题并调用自身来解决问题的部分。
递归算法的步骤
1. 问题定义：定义一个问题，并确定问题是否可以被分解为更小的子问题。
2. 确定基本情况：找出问题可以直接解决而不需要进一步递归的情况。
3. 确定递归步骤：描述如何将问题分解为更小的子问题，并递归调用算法来解决这些子问题。
4. 组合结果：如果递归调用返回结果，需要有一种方法来组合这些结果以解决原始问题。
示例：斐波那契数列
斐波那契数列是一个经典的递归问题，其中每个数字是前两个数字的和，定义为：F(n) = F(n-1) + F(n-2)，基本情况是F(0) = 0和F(1) = 1。
#include <iostream> using namespace std; // 递归函数来计算斐波那契数列的第n项 int fibonacci(int n) { if (n <= 0) { return 0; // 斐波那契数列的第0项是0 } if (n == 1) { return 1; // 斐波那契数列的第1项是1 } // 递归调用计算第n项 return fibonacci(n - 1) + fibonacci(n - 2); } int main() { int n; cin>>n; cout << fibonacci(n) << endl; return 0; }
递归算法的优点
1. 简洁性：递归算法通常可以用较少的代码行数来描述，使算法更易于理解和实现。
2. 自然映射：对于可以自然分解为子问题的问题，递归提供了一种直接的解决方案。
递归算法的缺点
1. 效率问题：递归算法可能会导致大量的重复计算，特别是对于没有优化的简单递归。
2. 栈溢出：深度递归可能导致栈溢出错误，因为每次递归调用都会占用一定的栈空间。
3. 理解难度：对于初学者来说，理解递归的概念和调试递归代码可能比较困难。
递归与迭代的比较
尽管递归算法在概念上很简洁，但在某些情况下，迭代算法可能更高效。迭代算法使用循环结构来模拟递归过程，通常可以避免重复计算和栈溢出的问题。在实际应用中，有时会使用递归的思想来设计迭代算法，例如通过显式地使用数据结构来保存中间结果。
尾递归优化
尾递归是递归函数的一类特殊形式，其中递归调用是函数体中的最后一个操作。尾递归可以被优化以减少栈空间的使用，因为当前函数的栈帧在递归调用返回时不再需要。在某些编程语言中，尾递归可以被编译器优化以避免增加额外的栈帧。
算法训练 进击的青蛙
资源限制
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s
问题描述
青蛙X正准备跳过一座桥，这座桥被划分为N段，记青蛙所在的起始点为0，桥的末端为N。桥上的一些点有一些石子，这些点是无法跳上去的。青蛙每次跳跃能向前跳跃+1，+2，+3段，现在请你算出跳到末端的总方法数。如果无法到达，请输出”No Way!"
输入格式
输入数据共N行。
第一行一个数字N，代表桥的长度。
接下来N行，表示从点1~N的道路情况，每行一个数字0或1，1表示有石子。
输出格式
输出一行，为一个整数，代表方法数，无法到达为“No Way!"
由于数据过大，我们只需要求出 对 1000000007 的余数即可
输出格式
输出一行，为一个整数，代表方法数，无法到达为“No Way!"
由于数据过大，我们只需要求出 对 1000000007 的余数即可
样例输入
5
1
0
0
1
0
样例输出
3
数据规模和约定
N <= 10^6
解题思路：
这道题一眼以为是搜索+回溯，但是看了一眼数据大小就感觉会超时，提交上去运行超时，所以会有更好的算法，然后就去看了okok__TXF大佬的思路，看了他们的博客都是用的dp+递推，是斐波那契的变形。具体思路讲解看注释吧。
代码实现：
#include<iostream> using namespace std; typedef long long ll; ll dp[1000005];//dp[i]表示从第0块石头到第i块石头的方法数 ll n; //斐波那契数列变形dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; //此青蛙一次能跳1，2，3步，所以只要求出dp[1],dp[2],dp[3]作为初值条件，利用递归求到n即可 int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>dp[i]; } //初值条件 dp[1]==0?dp[1]=1:dp[1]=0; dp[2]==0?dp[2]=dp[1]+1:dp[2]=0; dp[3]==0?dp[3]=dp[2]+dp[1]+1:dp[3]=0; for(int i=4;i<=n;i++){ if(dp[i]==1){//如果第i点不能跳，从0点无论怎样跳都不会到达第i点 dp[i]=0;//不能到达直接置0就可以了 }else{ dp[i]=(dp[i-1]%1000000007+dp[i-2]%1000000007+dp[i-3]%1000000007)%1000000007; } } if(dp[n]==0){//第n点根本就到达不了还有啥方法数 cout<<"No Way!"<<endl; }else{//如果dp[n]不为0那就是至少有一种可以到达的方法数 cout<<dp[n]%1000000007<<endl; } return 0; }
其实刚开始我也没想到是斐波那契的变形题，只有刷题刷多了就知道了，写了斐波那契也是通过了样例
本人小白一枚，如有错误请各位大佬指出，共同进步。
