递归，斐波那契数及其取模运算

一、递归 1、递归：即函数自己调用自己，函数在调用时会进行参数实例化，开辟栈空间。 2、递归可简化代码的编写。易读。 3、递归必须设置递归出口，否则会出现死循环 4、递归过程需一直开辟栈空间，运行速度慢，效率低。且存在栈溢出问题 5、相比较，迭代（非递归）的执行效率更高些，且不会一直开辟栈空间和造成栈的溢出问题，但代码书写量大，易读性低。

注：对一个数取模等同于对构成那个数的每个数取模， 列：13=8+5=8+3+2 那么 13%3=8%3+3%3+2%3=8%3+(3%3+2%3)%3 为防止每个数取模的和大于模数，所以每两个数取模之和后再次取模

二、代码实例解析（阶乘，斐波那契数及其取模运算）

#include<stdio.h>
#include<stdlib.h>

//54321输出5 4 3 2 1的递归执行流程解析
//递归是按一层一层的顺序执行的.
//只有当最内层执行结束后才执行上一层未执行的语句，每一层都为递归函数整体，但每层实际都不相同
//下列(num=5)：
//第n次执行表式 print用pn表式
//第n次执行表式 printf用pfn表式
//从外层到内层的顺序执行，只有当最内层执行结束后才接着执行上一层未执行的语句，因此最外层是最后执行结束的。
//(p1->( p2->(p3->(p4->(p5->pf5)->pf4->pf3)pf2)pf1)
//p2->(p3->(p4->(p5->pf5)->pf4->pf3)pf2
//p3->(p4->(p5->pf5)->pf4->pf3
//p4->(p5->pf5)->pf4
//p5->pf5

void print(int num)//num=5
{
 if(num>10)//递归出口条件
 {
  print(num/10);//digui. 54321-5432..->5
 }
 printf("%d  ",num%10);//5->4->3->2->1
}

int main()
{
  int num=0;
  printf("put num:");
  scanf("%d",&num);
  print(num);
  system(" pause");
  return 0;
}

//斐波那契数执行过程（若递归有多个return语句可画图求解分析）
//             change(5)//最终返回5，调用9次change()函数
//              /3  +  2
//     change(4)         change(3)
//       /  2+1          /  1+1  
// change(3) change(2)  change(2)  change(1)
//  / 1+1       1         1            1
//change(2) change(1)
//   1          1   //返回1结束本次调用   

#include<stdio.h>
#include<stdlib.h>

//斐波那契数：1+1+2+3+5+8 ....
int fbnqs(int num)//求第几个数的数值，当数值>40时计算速率很慢
{
    if(num<=2)
    {
        return 1;
    }
    return fbnqs(num-1)+fbnqs(num-2);
    //return fbnqs(num-1)%1007+fbnqs(num-2)%1007;//斐波那契数取模
}

//对一个数取模等同于对构成那个数的每个数取模，
//列：13%3=8%3+3%3+2%3=8%3+(3+2)%3
//为防止每个数取模的和大于模数，所以每两个数取模之和后再次取模，再加上下个数的余数，以此类推求出结果
//存储每个斐波那契数取模后的数而不是斐波那契数
int fbnqsy(int num)//迭代法，对斐波那契数（999）取模（10007）
{
    int a, b, c, i;
    a = 1;
    b = 1;
    if(num < 3) return 1;
    for(i = 3; i <= num; i++){
        c = (a + b) %10007;//前两个数的余数+下一个数的余数，
        a = b % 10007;//对取模的两个数再次取模防止之和大于模数,
        b = c;//前两个数的余数，
    }
    return c;
}

int change(int num)//计算结成
{
  if(num==1)//num==1时，退出函数
  {
  return num;
  }
  return num*change(num-1);//递归，累乘
}

int main()
{
 int num=0;
 printf("put num:");
 scanf("%d",&num);

 printf("%d 
",change(num));
 printf("%d 
",fbnqs(num));
 printf("%d 
",fbnqsy(num));
 system("pause");

 return 0;
}