递归在书写的时候，有两个必要条件：
1.递归存在限制条件，但凡满足这个限制条件时，递归便不再继续
2.每次递归调用之后越来越接近这个限制条件
递归的思想：
把大事化小事
递归其实就是函数自己调用自己
//int main() //{ // printf("hehe\n"); // main();//再次调用main函数自己 // return 0; //} 输出结果就是程序进入死循环，一直打印hehe 总而言之，在函数中再次调用自己就是递归 如果递归无限的递归下去，就会出现这样的错误，栈溢出 // 每一次函数调用，都要为这次函数调用分配内存空间是内存的栈区上分配的， 如果无限的递归调用函数，就会将栈区空间使用完， 就会出现栈溢出的现象
//递归---求n的阶乘 //n的阶乘就是1~n的数字累计相乘 //n!=n*(n-1)! //当n=0时，n的阶乘为1 //Fact(int n)//传参穿过来一个n //{ // if (n == 0) // return 1; // else if (n > 0) // return n * Fact(n - 1);//就是n*(n-1)! //} // // // //int main() //{ // int n = 0; // scanf_s("%d", &n); // int r = Fact(n);//n的阶乘 // printf("%d\n",r); // return 0; //} //当输入数字是5的时候，n传上去的n是5，因为n>0,所以进行n * Fact(n - 1)、 //也就是n*(n-1)! 5*4! //然后一次进行下去 //到最后，Fact（1）=1*Fact(0),因为Fact(0)=1，所以Fact（1）=1 //Fact（2）=2 //Fact（3）=6 //Fact（4）=24 //Fact（5）=120 //先递推再回归
//假设输入1234 // 1234%10=4 // 1234/10=123 // 123%10=3 // 123/10=12 // 12%10=2 // 12/10=1 // 1%10=1 // 1/10=0 //void print(int n)//接收n值 //{ // if (n > 9) // print(n / 10); // printf("%d ", n % 10);//打印余数 //} // //int main() //{ // int n = 0; // scanf_s("%d", &n); // print(n);//传过去n值 // // return 0; //} //假设n是123，大于9进去，先用print（123/10），把12的每一位打印出来 //上一步结束后，再打印123%10打印余数3 //原理： //print(1234) //print(123)+ 4 //print(12)+ 3 4 //print(1)+2 3 4 ***拆解到这一步然后返回依次打印 //代码的执行顺序是先print,再打印， //你输入的数据进入print一直被拆分，知道拆分为1时就停止了， // 然后再依次打印 //先是print(123) //然后又进入print(123/10)也就是print(12) //print(12)进去了print(12/10),也就是print(1), //最后因为1<9,所以就先开始打印了1%10了， //再返回打印12%10了，然后就是123%10 //最后的结果就是1 2 3 //只有print调用完才能轮到printf去打印 //print(1234)分成两部分-- - print（123）和printf（"%d", 4） //print(123)分成两部分---print（12）和printf（"%d",3） //print(12)分成两部分---print（1）和printf（"%d",2）
如果函数不返回，函数所对应的栈帧空间就会一直被占用
不使用递归，使用迭代---循环的方式来解决问题
循环一定是迭代，但迭代不一定是循环
//求n的阶乘---循环迭代 int Fact(int n) { int i = 0; int ret = 1; for ( i = 1; i <= n; i++) { ret *= i;//就是ret = ret * i } return ret; } int main() { int n = 0; scanf_s("%d", &n); int r = Fact(n); printf("%d", r); return 0; }
使用迭代的方式去求解，不仅可以解决问题，效率还更高
1 1 2 3 5 8 13 21 34 55
当n≤2时，第n个斐波那契数都是1，当n>2时，第n个斐波那契数就可以通过前两个数相加计算
若果求第n个斐波那契数列，用Fib(n)来表示，
当n>2的时候，Fib(n)=Fib(n-1)+Fib(n-2)
//求第n个斐波那契数 //若果求第n个斐波那契数列，用Fib(n)来表示， // //当n > 2的时候，Fib(n) = Fib(n - 1) + Fib(n - 2) int Fib(int n) { if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 2); } int main() { int n = 0; scanf("%d", &n); int r=Fib(n); printf("%d\n", r); return 0; }
当输入n为50，输出结果十分慢
//循环的方法求出第n个斐波那契数 //1 1 2 3 5 8 13 21 34 55 //求第3个数也就是求2，需要进行一次运算 //求第4个数的时候需要运算两次 //求第五个数的时候要运算3次。 //所以求第n个数的时候，要运算n-2次 int Fib(int n) { int a = 1; int b = 1; int c = 0; //n=1或者n=2的时候，可以不进入循环，n是3的时候大于2，就进去运算 while (n > 2)//仅仅只有当n>2的时候我们才进行计算 { c = a + b; a = b; b = c; n--;//当n是3的时候—1就是2，就不满足循环的条件 }//当n是4的=时候，c=1+1=2,然后b就变成下一个运算中的a了， //第一个运算的c也变成第二个运算中的b了，然后第四个要求的数就是c了， //第一次运算的时候运行了一次n--.所以变成了3，在第二次运行的时候再次 //运行就变成2了，就停止循环了 return c; //当n=1时，不执行循环，直接返回c //当n=2时，不执行循环，直接返回c } int main() { int n = 0; scanf_s("%d", &n); int r = Fib(n); printf("%d", r); return 0; }
