递归算法经典实例c

⑴ 1-100用c语言的递归法求和

C语言递归求和算法是一种简洁而优雅的方法。以1至100的整数和为例，我们可以用递归函数轻松实现。递归函数的定义如下：

#include <stdio.h>
int sum(int n) {
if (n == 1) return 1;
else return n + sum(n - 1);
}

这个函数首先检查输入的整数n是否为1。如果是，则直接返回1。否则，它将n与sum(n-1)的结果相加，并返回这个值。这个过程会一直递归下去，直到n减少到1。

在主函数中，我们设置变量i为100，并调用sum(100)函数计算1到100的和。通过printf函数输出结果：

int main(){
int i = 100;
printf("%d\n", sum(100));
return 0;
}

这段代码通过递归调用实现了累加操作，逐步将1到100的整数相加。递归的本质在于利用函数自身来解决问题，而这里则是利用递归逐步逼近问题的最基础情况。通过这样的方法，我们可以解决一系列复杂的数学问题，而无需复杂的循环结构。

递归求和的效率如何呢？对于这个问题，我们需要考虑递归调用的次数。在这个例子中，我们需要调用sum函数100次，每次调用都会产生一次递归。虽然递归求和的代码简洁明了，但它可能会导致栈溢出，特别是在处理较大范围的数字时。因此，在实际应用中，我们可能需要考虑使用迭代方法或其他更高效的算法。

递归求和算法展示了C语言的强大功能，同时也提醒我们，在选择算法时应考虑其适用性和效率。对于较小的范围，递归求和可能是最优解，但在某些情况下，迭代方法可能更为合适。

⑵ C语言背包问题递归算法

你学过数据结构了吗？如果学过，那就比较好理解，该算法的思路和求二叉树的高度的算法的思路是十分类似的。把取这i个物体看成i个阶段，则该二叉树有i+1层。其中空背包时为根结点，左孩子则为放弃了第1个物品后的背包，右孩子为选取了第1个物品后的背包。今后在对第i个物品进行选择时，向左表示放弃，向右表示选取。则递归算法可如下：
int fun(int s, int i, int n) //s传入的是背包容量, i是进行第i个物品的选取，n为剩余物品的件数
{
if(s == 0) return 有解；
else if(剩余的每件物品都装不进|| n == 0) return 无解；
L = fun(s, i + 1, n - 1); //放弃第i个物品，则下一步的背包容量仍为s，然后看其是否有解，(递归调用进入左子树)
R = fun(s - wi, i + 1, n - 1); //选取第i个物品，则下一步的背包容量为s-wi，然后看其是否有解，(递归调用进入右子树)
return (l, r); //综合考虑左右两边，看哪边是正解或都无解。其实应该返回 return (L||R);
}

⑶ C语言入门——递归(简要讲解+递归练习)

递归是一种程序设计技巧，即函数调用自身来解决问题，其核心概念是"递去(递推)+归来(回推)"。递归的主要目的是通过简化代码来表达复杂的重复计算，优点在于代码量相对较少，但其运行效率较低，因此在选择算法时应尽量避免递归，除非在没有其他更优解的情况下。

让我们通过实例来深入理解递归。首先，考虑斐波那契数列，其递推公式为F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)（n≥2）。递归实现时，可以解决求第n项的问题，如输入3时，输出2。再者，递归也可以用于计算阶乘，如输入5时，输出120，只需要理解n!的定义，即n!=n×(n-1)!，特别是对于0的阶乘，定义为1。

另一个实例是打印一个整数的每一位，例如输入13579，输出为1 3 5 7 9。通过递归，我们可以将复杂的问题拆分为更小的部分，然后逐个解决。

以上是递归的基本概念和应用，希望对初学者有所帮助。如果你对这些内容有任何疑问或发现错误，欢迎交流和指正。