递归

递归是个什么东西呢,从字面意思来理解好像是先给再还回来,事实上它也就是这个意思,从函数的角度讲就是自己调用自己。

如果以前没有学习过递归,看到下面的这个程序,你可能不理解什么意思。

#include
“stdio.h”

 

void wstring(int
n)

{

    if(n==0)

    {

        printf(我是第%d次调用了\n”,n);

        return;

    }

    else

    {

        printf(我是第%d次调用了\n”, n);

        wstring(n-1);

    }

}

 

int main()

{

    wstring(10);


return 0;

}

再改动一点细节,不知道是否好理解一些了。

#include
“stdio.h”

 

void wstring(int
n)

{

    if(n==0)

    {

        printf(我是第%d次调用了\n”,n);

        return;

    }

    else

    {

        printf(我是第%d次调用了\n”, n);

        n = n – 1;

        wstring(n);

    }

}

 

int main()

{

    wstring(10);


return 0;

}

这个程序确实不好理解,如果换成这样是不是很明确了。

#include
“stdio.h”

 

void wstring(int
n)

{

    for(int i=n;i>=0;–i)

    {

        printf(我是第%d次调用了\n”, i);

    }

}

 

int main()

{

    wstring(10);


return 0;

}

上述的例子就是递归,常用给出的例子是斐波那契数列,1,1,2,3,5,8,……,这个数列的通项公式即an=an-1+an-2,n>=3,如果用递归的写法,示例如下

#include
“stdio.h”

 

int Febo(int
n)

{

    if(n==1 || n==2)

    {

        return 1;

    }

    else

    {

        return Febo(n – 1) + Febo(n-2);

    }

}

 

int main()

{

    int m = 12;

    printf(%d项为:%d\n”, m,Febo(m));


return 0;

}

 

 

我们再用循环写一次

#include
“stdio.h”

 

int Febo(int
n)

{

    if (n == 1 || n == 2)

    {

        return 1;

    }

    else

    {

        int an1 = 1, an2 = 1, an3;

        for(int i=3;i<=n;++i)

        {

            an3 = an1 + an2;

            an1 = an2;

            an2 = an3;

        }

        return an3;

    }

}

 

int main()

{

    int m = 12;

    printf(%d项为:%d\n”, m,Febo(m));


return 0;

}

我看到相关的参考资料上说,递归和循环是可以相互转换的,我也不太确定是不是所有的情况都可以。

递归运算牵扯到压栈出栈操作,不仅花费的时间多而且占用的空间也多,容易造成溢出,你可以试一下用上面递归的方法求第100项的运算结果,你会发现消耗的时间比较长。

递归解决问题的思想还有很巧妙的。

2021年3月11日

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注