广场 › 编程语言 › c语言_Day16_07_17

影者东升 发表于 2021-7-18 10:19:17

c语言_Day16_07_17

c语言_Day16_07_17
1、递归分析
递归操作的本质为入栈与出栈
入栈：从递归头开始每自己调用1次便进行1次入栈操作，直到递归尾return
出栈：每return1次便进行1次出栈操作，直到递归头结束递归int my_strlen(char* str)
{
        if (str != 0)
        {
                return my_strlen(++str) + 1;
        }
        else
        {
                return 0;
        }
}

int main()
{
        char str[] = "abcdef";
        printf("%d\n", my_strlen(str));

        return 0;
}
[*]阶乘求解
int factorial(int num)
{
        if (num > 1)
        {
                return factorial(num - 1) * num;
        }
        else if (num == 1 || num == 0)
        {
                return 1;
        }
        else
        {
                return -1;
        }
}

int main()
{
        int num;
        scanf("%d", &num);

        printf("%d\n", factorial(num));

        return 0;
}
[*]求解斐波那契数
int Fib(int n)
{
        if (n <= 2)
        {
                return 1;
        }
        else
        {
                return Fib(n - 1) + Fib(n - 2);
        }
}

int main()
{
        int n = 20;
        printf("%d\n", Fib(n));

        return 0;
}然而，使用递归求解斐波那契数时，若递归层数过高会导致代码效率低下，故可使用循环进行优化
int Fib(int n)
{
        int fir = 1;
        int sec = 1;
        int ex;
        int count = 3;

        if (n <= 2)
        {
                return 1;
        }
        else
        {
                while (count <= n)
                {
                        ex = fir;
                        fir = sec;
                        sec = ex + sec;
                        count++;
                }
                return sec;
        }
}

int main()
{
        printf("%d\n", Fib(7));

        return 0;
}总结：简单理解，循环是递归的逆过程
2、递归问题

[*]效率低
当递归层过长，或进行大量重复计算时，递归的效率会极其低下，而使用循环可有效提升代码的运行效率

[*]栈溢出
void test()
{
        if(n < 10000)
      test(n + 1);
}上述代码符合递归的两个必要条件，但程序仍然会栈溢出，因此递归存在栈溢出的风险

文档来源：51CTO技术博客https://blog.51cto.com/u_15285915/3119518

查看完整版本: c语言_Day16_07_17