函数和递归（2） - HelloWorld开发者社区

#include <stdio.h>

int my_strlen(char* str)
{
    if (*str != '\0')
        return 1 + my_strlen(str + 1);
    else
        return 0;

}

int main()
{
    char arr[] = "Hello";
    int len = my_strlen(arr);
    printf("len=%d", len);
    return 0;
}

上述代码中第15行把数组arr传值给函数my_strlen，str接收到数组arr中第一个元素“H”的地址，第5行判断为真（“H”不是“\0”），执行第6行代码。 ::: tip return 1 + my_strlen(str + 1)中的“1”是表示经过第5行的判断，数组arr中第一个元素不等于“\0”,此时元素长度至少为1。 my_strlen(str + 1)中的str+1表示组arr中第一个元素“H”的地址再加1，即“e”的地址，经过第5行的判断，数组arr中第一个元素不等于“\0”,此时元素长度至少为1。以此循环，直到“\0”=“\0”，return 0返回到上一次调用时的位置，返回“1+0”的值到上上一次调用时的位置，再加1，直到返回到主函数。 :::

递归与迭代

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

求阶乘除了用循环的方式外，还可以使用递归方式：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

int Fac(int n)
{
    if (n <= 1)
        return 1;
    else
        return n * Fac(n - 1);
}

int main()
{
    int a = 0;
    scanf("%d", &a);
    int ret = 0;
    ret = Fac(a);
    printf("%d的阶乘为%d",a,ret);
    return 0;
}

5
5的阶乘为120

::: tip 阶乘的性质n(n-1)!=n!，即Fac(n)中当n<=1时，阶乘为1，n>1时，阶乘为n*Fac(n-1)。Fac(n-1)即(n-1)!。 :::

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

#include <stdio.h>

int Fib(int x)
{
    if (x <= 2)
        return 1;
    else
        return Fib(x - 1) + Fib(x - 2);
}

int main()
{
    int num = 0;
    scanf("%d", &num);
    int ret = 0;
    ret = Fib(num);
    printf("第%d个斐波那契数为%d",num,ret);
    return 0;
}

6
第6个斐波那契数为8

使用上述代码计算第50个斐波那契数时，需要计算很长时间。原因如下：

50
49 48
48 47 47 46
47 46 46 45 46 47 45 44

根据后一个数字是前两个数字的和，即第50个数字是第49和第48个数字的和，而第49个数字是第48和第47个数字的和，依次向下，计算量指数增加，加重运算负担，且有很多重复计算，浪费计算资源。如下：

#include <stdio.h>
int count = 0;
int Fib(int x)
{
    if (x == 3)  //测试第三个斐波那契数计算次数
        count++;
    if (x <= 2)
        return 1;
    else
        return Fib(x - 1) + Fib(x - 2);
}

int main()
{
    int num = 0;
    scanf("%d", &num);
    int ret = 0;
    ret = Fib(num);
    printf("第%d个斐波那契数为%d\n",num,ret);
    printf("第三个数字计算了%d次", count);
    return 0;
}

35
第35个斐波那契数为9227465
第三个数字计算了3524578次

上述结果中仅打印出第35个斐波那契数，就将第三个数字重复计算打印了3524578次，效率过低。 ::: warning 上述结果表明递归不适用于任何场景。 ::: 循环方法计算斐波那契数：

#include <stdio.h>

int Fib(int n)
{
    int x = 1;
    int y = 1;
    int z = 1;  //当n<3时，不进入循环，直接返回z。
    while (n > 2)
    {
        z = x + y;
        x = y;
        y = z;
        n--;  //前两个数是1，第三个数字是2，m=3时进入循环，m--变为2
    }
    return z;
}

int main()
{
    int m = 0;
    scanf("%d", &m);
    int ret = 0;
    ret = Fib(m);
    printf("%d", ret);
    return 0;
}

::: tip 第13行代码的分析：

1 1 2 3 5 8 13
1 2 3 4 5 6 7

上述数列中，要求第5个数字时候，只需要“1+1”、“1+2”、"2+3"三个步骤，即“z = x + y”只需要执行3次。 while判断5>2，执行一次z = x + y，n--，n由5变为4；再循环4>2，再执行一次z = x + y，n--，n由4变为3；再循环3>2，再执行一次z = x + y，n--，n由3变为2；while判断不成立，即return z。 :::

递归与迭代

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

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

热门文章