C语言学习记录---函数3

声明

#include<stdio.h>
#include<string.h>
#include<windows.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>

7.3 递归与迭代

7.3.1 练习3：

求n的阶乘。（不考虑溢出）

参考代码：

int Facl(int n)
{
    if(n > 1)
    {
        return n = n *Facl(n-1);
    }
    else
    {
        return 1;
    }

}

int main()
{
    int n = 0;
    int ret = 0;
    printf("请输入n的值>:");
    scanf("%d",&n);
    ret = Facl(n);
    printf("%d\n",ret);
    return 0;

}

//
int Facl(int n)
{
    int i = 0;
    int ret = 1;
    for(i = 1;i<=n;i++)
    {
        ret *= i;
    }
    return ret;
}
int main()
{
    int n = 0;
    int ret = 0;
    printf("请输入n的值>:");
    scanf("%d",&n);
    ret = Facl(n);
    printf("%d\n",ret);
    return 0;

}

7.3.2 练习4：

求第n个斐波那契数。（不考虑溢出）

参考代码：

int Fib(int n)
{
    if(n >2)
    {
        return n = Fib(n-1)+Fib(n - 2);
    }
    else
    {
        return 1;
    }
}


int main()
{
    int n = 0;
    printf("你想知道第几个斐波那契数>:");
    scanf("%d",&n);
    int fib = Fib(n);
    printf("%d",fib);
    return 0;
}





这种方法计算量大，多加两行代码测第三个斐波那契数的个数，
当n足够大时，仅是第三个斐波那契数的计算次数就非常大；
所以这里用递归不合适
int count = 0;
int Fib(int n)
{
    if(n ==3)
    {
        count ++;
    }
    if(n >2)
    {
        return n = Fib(n-1)+Fib(n - 2);
    }
    else
    {
        return 1;
    }
}

int main()
{
    int n = 0;
    printf("你想知道第几个斐波那契数>:");
    scanf("%d",&n);
    int fib = Fib(n);
    printf("%d",fib);
    printf("count = %d",count);
    return 0;
}

改进
int Fib(int n) 
{
    int a = 1;
    int b = 1;
    int c = 1;
    while(n >2);
    {
        c = a+b;
        a = b;
        b = c;
        n --;
    }
    return c;
}

int main() {
    int n = 0;
    printf("你想知道第几个斐波那契数>:");
    scanf("%ld", &n);
    int fib = Fib(n);
    printf("%ld", fib);
    return 0;
}
//但当n比较大时，因为数字比较大，会出现溢出

在调试函数的时候，如果你的参数比较大，那就会报错： stack overflow（栈溢出）这样的信息。

系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一 直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出

那如何解决上述的问题：

1. 将递归改写成非递归。

2. 使用static对象替代 nonstatic 局部对象。在递归函数设计中，可以使用 static 对象替代nonstatic 局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销，而且 static 对象还可以保存递归调用的中间状态，并且可为各个调用层所访问

//求n的阶乘
int factorial(int n)
{
        int result = 1;
        while (n > 1)
       {
             result *= n ;
             n -= 1;
       }
        return result;
}
//求第n个斐波那契数
int fib(int n)
{
     int result;
     int pre_result;
     int next_older_result;
     result = pre_result = 1;
     while (n > 2)
     {
           n -= 1;
           next_older_result = pre_result;
           pre_result = result;
           result = pre_result + next_older_result;
     }
     return result;
}

提示：

1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开

销。