函数和递归(2)

似梦清欢
• 阅读 485
#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。 :::

点赞
收藏
评论区
推荐文章

暂无数据

似梦清欢
似梦清欢
Lv1
学海无涯
文章
17
粉丝
17
获赞
1