C语言：递归算法

一：递归的概念，什么是递归算法？

递归函数最通俗的讲法就是先传递，在一次一次的传递后再归来！

下面这个图能够很好的解释出递归函数的主要工作原理（红线先走绿线跟后）

void fun(int n)
{if (n > 9){fun(n/10);}printf("%d ", n % 10);
}

递归作为一种非常常用的算法，其本身定义为一个过程或函数在其定义或说明中有直接或间接

递归算法有两个必要条件：

1.存在一个限制条件，使得满足这个条件时，递归能够主动不再继续进行。

2.在每次递归调用后，都必须更接近这个限制条件。

（在我个人看来，递归算法更像是一个循环，将该循环独立到一个函数中去，使后面使用时更方便！在我们写一个递归函数时，必须要明白使用这个函数是为了求什么，这个函数的功能是什么！函数的功能应该更简谱，单一！不应掺杂进去别的与写该函数目的不相符的代码！
例如：

//递归方式求阶乘(不考虑溢出问题！)
int fac(int n)
{if (n <= 1){return 1;}return n * fac(n-1);
}

上面是一个求阶乘的递归函数，其主要功能就是求一个数的阶乘，因此我们不应该在其中加入输入，输出等等功能！）

二：递归函数的运用。

（递归函数最主要，也是最难的一部就是寻找一个等价关系式，使得在一次一次的使用递归时能够更接近自己的目的！）

斐波那契数列

斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34…，即第一项 f(1) = 1,第二项 f(2) = 1…,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。 

首先，我们要明白用递归写这个函数的主要功能是找到第n项的值是多少？

我们观察数列，前两项为1，第三项为前两项的和，第四项等于第二 三项的和，因此我们可以得出一个结论，第n项等于第（n-1）与第（n-2）项的和！

同时，我们应该注意到两个必要条件，存在一个限制条件，每次递归后更接近该递归函数！（每次运算都要在n的基础上-1，知道n=1或者n=2时停止！

因此我们可以写出一下代码

int finbo(int n)
{if (n == 1 || n == 2){return 1;}else{return finbo(n - 1) + finbo(n - 2);}
}

一个有明确，唯一功能的递归函数就写出来了！！！！！

最终代码如下

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
#include
int finbo(int n)
{if (n == 1 || n == 2){return 1;}else{return finbo(n - 1) + finbo(n - 2);}
}
int main()
{int n;scanf("%d", &n);int m = finbo(n);printf("%d", m);return 0;
}

总结：

递归算法在初期使用时有一定的困难，但在刷一道一道题之后，对该算法就能较好的掌握，最主要就是找等价关系式，找出限制条件！！！

（注：本文为原创作品，若无意侵权，请联系我。）

欢迎点赞 👍 关注收藏 ⭐留言 📝  

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！