Recursion

递归生成某集合的所有序列:

template <class T>
void Swap(T& a, T& b)
{
   T temp = a;
   a = b;
   b = temp;
}

template <class T>
void Permulation(T list[], int k, int m)
{
   if (k == m)
   {
      for (int i = 0; i <= m; i++)
         cout << list[i];
      cout << endl;
   }
   else
   {
      for (int i = k; i <= m; i++)
      {
         Swap(list[k], list[i]);
         Permulation(list, k+1, m);
         Swap(list[k], list[i]);
      }
   }
}

递归生成某集合的所有子集:

思想:
设集合X (A1, A2, A3,…, An)的所有子集为S[X(n)],从集合X中移走A1的子集X(n-1)的所有子集集合记为S[X(n-1)]
S[X(n)] = S[X(n-1)] ∪ {S[X(n-1)]每个子集加上A1}
例如 集合{A, B, C}
{A}:
{} {A}
{A B}:
{} {A} ∪ {B} {A B}
{A B C}:
{} {A} {B} {A B} ∪ {C} {A C} {B C} {A B C}

template <class T>
void FindSubSets(T list[], int lowIndex, int highIndex, vector< set<T> > &results)
{
   if (lowIndex == highIndex)
   {
      set<T> empty;
      set<T> oneElem;
      oneElem.insert(list[lowIndex]);
      results.push_back(empty);
      results.push_back(oneElem);
   }
   else
   {
      FindSubSets(list, lowIndex+1, highIndex, results);
      int existedSetSize = results.size();
      for (int jj = 0; jj < existedSetSize; jj++)
      {
         set<T> newSet(results[jj]);
         newSet.insert(list[lowIndex]);
         results.push_back(newSet);
      }
   }
}

斐波那契数列计算:

递归:
int r_Fibonacci(int n)
{
   if ( n < 2)
      return n;
   return r_Fibonacci(n-1) + r_Fibonacci(n-2);
}

非递归:
int fibonacci(int n)
{
   if ( n < 2)
      return n;
   int f0 = 0;
   int f1 = 1;
   for (int ii = 1; ii < n; ii++)
   {
      f1 = f1 + f0;
      f0 = f1 - f0;
   }
   return f1;
}

递归查找:

template <class InputIter, class T>
InputIter find(InputIter begin, InputIter end, const T& val)
{
   if (begin != end && *begin != val)
      return find(begin+1, end, val);
   else
      return begin;
}

Leave a Reply

Your email address will not be published. Required fields are marked *