C语言中的递归问题

Question

3．有一个糊涂人，他写了n封信和n个信封，到了邮寄的时候，把所有的信都装错了信封。设Dn为n封信封可能的种类数，可以用下面的递归
公式：Dn=(n-1)(Dn-1+Dn-2)
D2=1
D1=0
请分别用递归和递推方法编程计算Dn，n由键盘输入。
谢谢大家啦

Answer 1

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。

递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

扩展资料：

递归的应用

1、数据的定义是按递归定义的。（Fibonacci函数）

2、问题解法按递归算法实现。这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。

3、数据的结构形式是按递归定义的。

递归的缺点

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

参考资料来源：百度百科-递归

Answer 2

// 下面的代码可以完成你的要求，仅供参考。

#include <stdio.h>
#include <stdlib.h>

int GetD1(int n, int *D);
int GetD2(int n);

int main(int argc, char *argv[])
{
int n;
int D;
if (argc != 2)
{
printf("Usage: %s number\n", argv[0]);
exit(0);
}
n = atoi(argv[1]);

printf("递归: %d\n", GetD1(n, &D));

printf("递推: %d\n", GetD2(n));

return 0;
}

int GetD1(int n, int *D)
{
if (n <= 1)
{
*D = 0;
return 0;
}
else if (n == 2)
{
*D = 0;
return 1;
}
else
{
int m = GetD1(n - 1, D);
int k = (n - 1) * (m + *D);
*D = m;
return k;
}
}

int GetD2(int n)
{
int i;
int j;
int sum[2] = {1, 0};

if (n <= 1)
{
return 0;
}
else if (n == 2)
{
return 1;
}
for(i = 3; i <= n; i++)
{
j = sum[0];
sum[0] = (i - 1) * (sum[0] + sum[1]);
sum[1] = j;
}
return sum[0];
}

Answer 3

GetDn(int n)
{
if (n == 1)return 0;
else if (n == 2)return 1;
else return (n-1) * (GetDn(n-1) + GetDn(n-2));
}

Answer 4

#include<stdio.h>
main()
{
int CalDn(int m);
int n;
printf("please input n :");
scanf("%d",&n);
printf("Dn is :%d\n",CalDn(n));
}

int CalDn(int m)
{
if(m==1) return 0;
else if(m==2) return 1;
else return (m-1)*(CalDn(m-1)+CalDn(m-2));
}本回答被网友采纳