C++递归函数

来源：百度知道 编辑：UC知道 时间：2024/06/02 02:16:41
#include <iostream.h>
#define MAXN 100
int a[MAXN], r[MAXN];
void rd(int n,int k)
{
int i,j;

for(j= n<a[k-1]? n:a[k-1] ; j>=1; j--)
{
a[k] = j;
if( j==n )
{
cout<<a[0]<<'='<<a[1];
for(i=2;i<=k;i++)
{
cout<<'+'<<a[i];
}
cout<<endl;
}
else
rd(n-j,k+1) ;
}
}
int test_data[]={3,4,5};
void main()
{
for(int i=0; i<sizeof(test_data)/sizeof(int); i++)
{
cout<<"------------------------------"<<endl;
a[0] = test_data[i];
rd(test_data[i],1 );
}
return;
}
请分析rd()函数实现递归的过程。

先理解函数的功能:
void rd(int n,int k);
在数组a[MAXN]上,从a[k]项起展开总和为n的1~n个数(要展开n次),且a[k]项的值得小于a[k-1]

所以分析如下:
比如测试数字为5时(下面的j数字表示第几级函数中的变量j,在递归逐级展开前,j5等没有值)
(楼主把下面的表复制到txt文本里面就对齐了,百度吃空格,不能用空格..)

j1__j2__j3__j4__j5__a0__a1__a2__a3__a4__a5
5___________________5___5_________________因为n1和a[0]都为5,所以j1=5
4___1_______________5___4___1_____________j1减一,因为n2为1,小于a[1],j2=n2
3___2_______________5___3___2_____________j1减一,n2为2,小于a[1],所以j2=n2
3___1___1___________5___3___1___1_________j2减一,n3为1等于a[2],所以j3=n3=1
2___2___1___________5___2___2___1_________j1减一,n2为3大于a1,所以j2=j1=2,然后n3=1,则j3=n3=1
2___1___1___1_______5___2___1___1___1_____j2减一,n3为2大于a[2],所以j3=a[2]=1,余下为1
1___1___1___1___1___5___1___1___1___1___1_j1减一,n2为4大于a[1],所以j2=a[1]=1,余下为1

这个递归的思想是,a[0]为要拼凑的数,然后从k=1开始逐位确定拼凑的解,通过逐渐减小低位置上的数,带动改变高位置上的数.
这里人为规定了地位置上的数要大于高位置上的数,言下之意,拼凑的解是组合,位置没有作用.这样就避免了重复解.(添加a[k]<a[k-1]的条件,避免了出现3=2+1和3=1+2这种重复情况)