递归转化成循环的算法实现

 有些递归是很容易转化成循环的，用一个循环非常直观的映射过去就是了，如求Fibonacci数列； 而有些递归却没有那么直观，甚至可能需要多个循环才能转化过去，这里举个例子：

给出一个集合，如(1, 2, 3, 4)，打印出该集合的所有子集
分析一下问题，子集是指取原集合中的任意多个元素，转化一下问题，就是对于原集合中的任何一个元素，我们都有两个选择，包含或者不包含，所以对于n个元素的集合，其子集数为： 2*2*2... = 2^n。那么可以得出其递归算法：

01 void Recursive_Subsets(int* a, bool* b, int start, int end)

02 {

03 if (start <= end)

04 {

05 // determine current number's status, which has 2 choices

06 // and then continue with left ones

07 b[start] = true;

08 Recursive_Subsets(a, b, start+1, end);

09

10 b[start] = false;

11 Recursive_Subsets(a, b, start+1, end);

12 }

13 else

14 {

15 for (int i = 0; i <= end; i++)

16 {

17 if (b[i]) cout << a[i];

18 }

19 cout << endl;

20 }

21

22 }

23

24 void PrintAllSubsets1(int* a, int n)

25 {

26 bool* b = new bool[n];

27 Recursive_Subsets(a, b, 0, n-1);

28 delete b; 
29 }

递归的优点是直观、易懂：写起来如此，读起来也是这样。但是每次递归都是call stack的不断叠加，对于这个问题，其需要消耗O(n)的栈空间，栈空间，栈空间~~~

于是，我们也可以将其转化成循环的方式来实现：

01 void PrintAllSubsets2(int* a, int n)

02 {

03 // Initialize flags as false

04 bool* b = new bool[n];

05 for(int i = 0; i < n; i++)

06 {

07 b[i] = false;

08 }

09

10 // Use 2 loops to enumerate all possible combinations of (each item's status * number of items),

11 // in this case: ([true|false] * size of set)

12 while(true)

13 {

14 // Get one solution, output it!

15 for(int i = 0; i < n; i++)

16 {

17 if(b[i]) cout << a[i];

18 }

19 cout << endl;

20

21

22 // One of the number's status has switched, start over enumeration for that!

23 // ex: I have following enumeration for 3 numbers:

24 // 0, 0, 0

25 // 0, 0, 1

26 // 0, 1, 0

27 // 0, 1, 1

28 // now if I changed the first number's status from 0 to 1, I need to re-enumerate the other 2 numbers

29 // to get all possible cases:

30 // 1, 0, 0

31 // 1, 0, 1

32 // 1, 1, 0

33 // 1, 1, 1

34 int k = n - 1;

35

36 while(k >= 0)

37 {

38 if(b[k] == false) // have we tried all possible status of k?

39 {

40 b[k] = true; // status switch, as we only have 2 status here, I use a boolean rather than an array.

41 break; // break to output the updated status, and further enumeration for this status change, just like a recursion

42 }

43 else // We have tried all possible cases for k-th number, now let's consider the previous one

44 {

45 b[k] = false; // resume k to its initial status

46 k--; // let's consider k-1

47 }

48 }

49

50 if(k < 0) break; // all the numbers in the set has been processed, we are done!

51 }

52

53 // clean up

54 delete [] b;

55 }

详细如何转换在注释中已经说明，对于这类穷举状态的递归程序，我们可以将这个程序的框架当做一个模式，照样子来转化即可。