函数递归超详解！

目录
 1.什么是递归调用？
直接调用
         间接调用
2.什么是递归？
3.递归举例
3.1求n!的阶乘
3.1.1.非递归法
3.1.2.递归法
3.1.2.1分析和代码实现
3.2次序打印一个整数的每一位
3.2.1分析和代码实现
4.递归与迭代
4.1举例：斐波那契数列
4.1.1迭代法
4.1.2递归法

---

 1.什么是递归调用？

   在调用一个函数出现直接或间接地调用该函数自己，称为函数的递归调用
  直接调用

1. void f()
2. {
3. ...
4. ...
5. f();//调用语句
6. ...
7. }

复制代码

间接调用

(下面这个代码中f函数调用了g函数，g函数又调用了f函数)

1. void f()
2. {
3. ...
4. ...
5. g();//调用g函数
6. ...
7. }
8. void g()
9. {
10. ...
11. ...
12. f();//调用f函数
13. ...
14. }

复制代码

   从以上两个函数可以看到，这两种递归调用都是无停止的自身调用。显然，程序中不应该出现这种无停止的递归调用，而只应该出现有限次数的、有停止的递归调用，这可以用if语句来控制，只有在某一条件建立时才继续实行递归调用；否则就不在继续。
  2.什么是递归？

   递归中的递就是递推，归就是回归
  
3.递归举例

3.1求n!的阶乘

3.1.1.非递归法

在进入递归之前，先领会一下非递归法

1. #include<stdio.h>
2. int   fac (int  n)   //n为形参
3. {  
4.     int i,m=1;
5.     for(i=1;i<=n;i++)
6.     {
7.         m=m*i; //用循环累乘：m=1*2*...*n
8.     }
9.    return m;
10. }
11. int  main()
12. {
13.     int n,y;
14.     scanf("%d",&n);//输入n
15.     y=fac(n);//n为实参
16.         printf("%d!=%d",n,y);
17. return 0;
18. }

复制代码

   （注：实参和形参可以重名，如果主程序中输入n值是4，调用函数时，则是把其值4传递给函数的形式参数n,形参n的值即为4，实参仅是做的一个值的传递，这个过程与实参的名字是什么无关，所以形参和形参名字雷同不影响传值调用）
  3.1.2.递归法

3.1.2.1分析和代码实现

   n!=n*(n-1)!
  4!=4*3*2*1
  3!=3*2*1
  所以：4！=4*3！
   

当n==0的时候，阶乘为1，其余用公式计算
先将整体代码列给各人

1. #include"stdio.h"
2. int fact(int n)
3. {
4.         if(n==0)
5.                 return 1;
6.         else
7.                 return n*fact(n-1);
8. }
9.        
10. int main()
11. {
12.         int n=0;
13.         scanf("%d",&n);
14.         int r=fact(n);
15.         printf("%d!=%d",n,r);
16.     return 0;
17. }

复制代码

下面用n=5时的例子给各人表明

   fact(5)固然=5*fact(4),但是fact（4）又是一个调用函数，再次调用fact函数，然后求得fact（4）为多少后，别忘记乘上前面的5，也可按照上图一步一步算
  由于你调用完得出的值得返回去
  
递归是用少量的代码完成大量复杂的运算 
3.2次序打印一个整数的每一位

   分析：输入一个整数，按照次序打印一个整数的每一位
  eg:
  输入：1234 输出：1 2 3 4
  3.2.1分析和代码实现

   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
  以上的方法很容易理解，但是过于复杂，所以下面我们用递归的方法解决此问题

 
仔细分析上图解析，可以的得出此代码为

1. #include<stdio.h>
2. void print(int n)
3. {
4.         if (n > 9)
5.                 print(n / 10);
6.         printf("%d ", n % 10);
7. }
8. int main()
9. {
10.         int n = 0;
11.         scanf_s("%d", &n);
12.         print(n);
13.         return 0;
14. }

复制代码

4.递归与迭代

fact函数是可以产生准确的效果，但是在递归函数中涉及一些运行时的开销。
   在c语言中每一次函数调用，都必要为本次函数调用在内存的栈区申请一块内存空间来保存函数调用期间的各种局部变量的值，这块空间被称为运行时堆栈，或者函数栈帧。
  函数不返回，函数对应的栈帧空间就不停占用，所以函数调用中存在递归调用的话，每一次递归调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，开始回归，才逐层开释栈帧空间。
  所以如果接纳函数递归的方式完成代码，递归条理太深，就会浪费太多的栈帧空间，也可能引起栈溢出的问题。
   
  所以我们可以利用迭代的方法（循环） 
 

1. #include<stdio.h>
2. int fact(int n)
3. {
4.         int i = 0;
5.         int ret = 1;
6.         for (i = 1; i <= n; i++)
7.         {
8.                 ret *= i;
9.         }
10.         return ret;
11. }
12. int main()
13. {
14.         int n = 0;
15.         scanf_s("%d", &n);
16.         int r = fact(n);
17.         printf("%d", r);
18.         return 0;
19. }

复制代码

注：当一个问题非常复杂，难以用迭代的方法实现时，此时递归实现的简洁性便可以赔偿它所带来的开销。
4.1举例：斐波那契数列

4.1.1迭代法

1. #include<stdio.h>
2. int fib(int n)
3. {
4.         int a = 1;
5.         int b = 1;
6.         int c = 1;
7.         while (n > 2)
8.         {
9.                 c = a + b;
10.                 a = b;
11.                 b = c;
12.                 n--;
13.         }
14.         return c;
15. }
17. int main()
18. {
19.         int n = 0;
20.         scanf_s("%d", &n);
21.         int r=fib(n);
22.         printf("%d\n", r);
23.         return 0;
24. }

复制代码

4.1.2递归法

1. #include<stdio.h>
2. int count = 0;
3. int fib(int n)
4. {
5.         if (n == 3)
6.                 count++;
8.         if (n <= 2)
9.                 return 1;
10.         else
11.                 return fib(n - 1) + fib(n - 2);
12. }
13. int main()
14. {
15.         int n = 0;
16.         scanf_s("%d", &n);
17.         int r=fib(n);
18.         printf("%d\n", r);
19.         printf("%d", count);
20.         return 0;
21. }

复制代码

  注意：此题利用迭代法（非递归法）更好，由于递归法计算时，会有重复计算， 下图我们看到，
  在计算第40个斐波那契数列时，第三个斐波那契数被重复计算了39088169次，这就会非常复杂。
  而用迭代是，从小往大加就行了。
  

 


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。