引言：
我在復習C++遇到了設計遞歸函數的問題。這個例子，很好的顯示了設計遞歸的方式，思想。
這與斐波那數列不同，這個例子更有應用意義。
問題：
試編寫一個遞歸函數，用來輸入n個元素的所有子集。
例如：三個元素{a,b,c}
輸出：
{a,b,c}
{ab}
{ac}
{bc}
{a}
{b}
{c}
{}
設計思路：
首先，遞歸是使用的if else結構。
然後，就是if中填條件，再在else寫調用自身的函數。
詳細思路，請看代碼。
代碼：
#include <string.h>
#include <iostream> using namespace std;
void build(char str[],int n)
{
if(n==0)//控制輸出
{
cout<<"{";
for(int i=0;i<5;++i)
if(str[i]!=' ')
{
cout<<str[i];
}
cout<<"}"<<endl;
}
else
{
/*** 先遞歸 ***/
build(str,n-1);
if(n>0)
{
char newstr[5] = {' '};//去掉就把該位置的元素置成空
/*** 還原之前的狀態 ***/ strcpy(newstr,str); /*** 越來越少的元素 ***/
newstr[n-1]= ' ';
/*** 再次遞歸 ***/
build(newstr,n-1);
}
}
}
測試代碼：
/***
將整個搜索過程表示為搜索樹的形式，問題自然就很簡單了。
每一個元素對於一個子集來說，只有兩中狀態：0表示不屬於該子集，1表示屬於該子集。
程序中的數組a就是采用這種表示。
因此，搜索過程表示為樹的形式就是這樣的：
a
0/ \1
b c
0/ \1 0/ \1
...........
因此：
代碼中的第一個“trail(t,i+1,n);”就是搜索當前擴展節點的左子樹（因為a[i]此時的值為0）。
代碼中的“a[i]=1-a[i];”就是變換當前擴展節點的狀態，也就是從左子樹換到右子樹。
代碼中的第二個“trail(t,i+1,n);”就是搜索當前擴展節點的右子樹。
***/
#include <string.h>
#include <iostream>
using namespace std;
void build(char str[],int n)
{
if(n==0)//控制輸出
{
cout<<"{";
for(int i=0;i<5;++i)
if(str[i]!=' ')
{
cout<<str[i];
}
cout<<"}"<<endl;
}
else
{
/*** 先遞歸 ***/
build(str,n-1);
if(n>0)
{
char newstr[5] = {' '};//去掉就把該位置的元素置成空
/*** 還原之前的狀態 ***/
strcpy(newstr,str);
/*** 越來越少的元素 ***/
newstr[n-1]= ' ';
/*** 再次遞歸 ***/
build(newstr,n-1);
}
}
}
int main()
{
char string[5]= "abc ";//實例集合放在數組中
build(string,3);
return 0;
}
其實，設計遞歸的關鍵是如何設計。想不到，就百度。看代碼也是個快樂的過程，關鍵是仔細思考。
囫囵吞棗，對於程序員是要不得了。如果你無法做到，用手到後拈來。那麼，你學習這個東西是失敗的！
