C# 递归转循环代码写法

作者:袖梨 2022-06-25

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

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

void printallsubsets2(int* a, int n)
{
 // initialize flags as false
 bool* b = new bool[n];
 for(int i = 0; i < n; i++)
 {
  b[i] = false;
 }

 // use 2 loops教程 to enumerate all possible combinations of (each item's status * number of items),
 // in this case: ([true|false] * size of set)
 while(true)
 {
  // get one solution, output it!
  for(int i = 0; i < n; i++)
  {
   if(b[i]) cout << a[i];
  }
  cout << endl;


  // one of the number's status has switched, start over enumeration for that!
  // ex: i have following enumeration for 3 numbers:
  //     0, 0, 0
  //    0, 0, 1
  //    0, 1, 0
  //    0, 1, 1
  // now if i changed the first number's status from 0 to 1, i need to re-enumerate the other 2 numbers
  // to get all possible cases:
  //     1, 0, 0
  //    1, 0, 1
  //    1, 1, 0
  //    1, 1, 1
  int k = n - 1;

  while(k >= 0)
  {
   if(b[k] == false) // have we tried all possible status of k?
   {
    b[k] = true; // status switch, as we only have 2 status here, i use a boolean rather than an array.
    break;   // break to output the updated status, and further enumeration for this status change, just like a recursion
   }
   else    // we have tried all possible cases for k-th number, now let's consider the previous one
   {
    b[k] = false; // resume k to its initial status
    k--;   // let's consider k-1
   }
  }

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

 // clean up
 delete [] b;
}


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

给出一个集合,如(1, 2, 3, 4),打印出该集合的所有子集

相关文章

精彩推荐