c语言_Day16_07_17

影者东升

c语言_Day16_07_17
1、递归分析
递归操作的本质为入栈与出栈
入栈：从递归头开始每自己调用1次便进行1次入栈操作，直到递归尾return
出栈：每return1次便进行1次出栈操作，直到递归头结束递归

int my_strlen(char* str)
{
    if (str[0] != 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);
}

上述代码符合递归的两个必要条件，但程序仍然会栈溢出，因此递归存在栈溢出的风险