C语言经典递归算法之和式分解

一、递归算法

1、递归
递归就是自己调用自己，它是设计和描述算法的一种有力工具，常常用来解决比较复杂的问题。
递归是一种分而治之，将复杂问题转化难为简单的问题的求解方法。

2、递归的优点
使用递归编写的程序简洁、结构清晰，程序的正确性很容易被证明，不需要了解递归调用的具体细节。

3、递归的缺点
递归函数在调用过程中，每一层调用都需要保存临时变量和返回地址、传递参数，因此递归函数的执行效率低。

二、和式分解

1、原理分析
（1）引入数组a，用来存放分解出来的和数，其中，a[k]存 放第k步分解出来的和数。

（2）递归函数应设置三个参数：第1个参数是数组名a,用来将数组中的元素传递给被调用函数；
第2个参数i表示本次递归调用要分解的数；
第3个参数k是本次递归调用将要分解出的第k个和数。

2、C语言实现和式分解

#include <stdio.h>
#define N 50
void rd(int a[], int i, int k);
void main()
{
	int n, a[N];
	printf("请输入一个正整数：n(0<=n<50)：");
	scanf("%d",&n);
	a[0]= n;
	printf("和式分解结果：\n");
	rd(a,n,1);
}
void rd(int a[], int i, int k)
{
	int j, p;
	for(j=i; j>=1; j--)
	{
		if(j<=a[k-1])
		{
			a[k]=j;
			if(j==i)
			{
				printf("%d=%d",a[0],a[1]);
				for(p=2; p<=k; p++)
					printf("+%d", a[p]);
				printf("\n");
			}
			else
				rd(a, i-j, k+1);
		}
	}
}

参考文献：《The Function and Algorithm of Program Language C/C++》