【Hello Algorithm】认识一些简单的递归

本篇博客介绍： 认识一些简单的递归

我在刚刚学习C语言的时候写过一个汉诺塔问题 大家可以参考下我之前写的这篇博客

汉诺塔问题

其实这个问题也可以这么解决

• 我们设计六个函数 这六个函数分别代表从a到b 从a到c …
• 但是实际上我们使用了一个函数就解决了上面六个函数才能解决的事

这就说明 我们可以使用增加参数的方式来增加递归函数的可能性

打印一个字符串全部的子序列

题目要求如下

假设字符串String str = “abc”，那么它的子序列有" "、a、b、c、ab、ac、bc、abc。依次从头往后拿，所有情况都枚举即可

我们回顾下题目实际上就是从第一个字符串开始我们考虑每个字符要和不要两种情况

那么我们可以设计这样子的一个递归函数

void process(string str ,int index , list<string> ans , string path)
1

这四个参数分别代表着

• 我们要传入的字符串
• 现在走到的位置
• 答案
• 目前为止拼接的字符串

我们每个递归函数内部只需要考虑当前字符是否拼接 之后传递给下一个递归函数即可

完整代码如下

  
  void process(const string& str ,int index , list<string>& ans , string path1)
  {
    if (str.length() == index)
    {
      ans.push_back(path1);
      return;    
    }    
      
    process(str , index + 1 , ans , path1);    
    process(str , index + 1 , ans , path1 + str[index]);    
  }
1
2
3
4
5
6
7
8
9
10
11
12

如果不允许有重复的字符串出现应该怎么做呢？

此时我们就可以使用 unordered_set 容器来自动去重即可

打印一个字符串的全排列

输入一个字符串 打印这个字符串的全排列

比如说给你一个字符串 abc

实际上就是给你一个字符集合 {a, b, c} 要求你将这三个字符随意组合出一个新的字符 共有多少种排列方式

实际上就是 3 x 2 x 1 一共六种

我们解决这个问题使用递归来解决 首先递归函数的声明如下

void  process(vector<char> lc , list<string>& ans , string path1)
1

代码如下

  void  process(vector<char> lc , list<string>& ans , string path1)    
  {    
    if (lc.size() == 0)    
    {    
      ans.push_back(path1);    
      return;    
    }    
    else    
    {    
      for (int i = 0; i < lc.size(); i++)    
      {    
        char cur = lc[i];    
        lc.erase(lc.begin() + i);    
        process(lc , ans , path1 + cur);                                                                                        
        lc.insert(lc.begin() + i , cur);    
      }    
    }    
  }  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

解释下上面这段代码 我们每次都从集合中拿走一个元素 如果说集合被拿空了 那么此时的字符串肯定已经拼接完成了

如果集合还没空我们就一个个将这些字符串拼接起来 （注意！ 如果你是将集合拼接在path中则要在最后还原path 如果是将path和cur一起传递则不用）

最后我们就能得到一个字符串的全排列了

当然 我们上面写的其实是一种不太好的递归 因为它可变参数的设计不太行 这样子我们递归到动态规划就会很麻烦 优秀的递归设计应该是下面这样子的

  void process(vector<char>& nums , int index , vector<string>& ans)    
  {    
    if (nums.size() == index)    
    {    
      string ans1;    
      for (auto x : nums)    
      {    
        ans1 += x;    
      }    
      ans.push_back(ans1);    
      return;    
    }    
    else    
    {    
      for (size_t i = index ; i < nums.size() ; i++)    
      {    
        swap(nums[i] , nums[index]);    
        process(nums , index + 1 , ans);    
        swap(nums[i] , nums[index]);    
      }                                                                                                                         
    }    
  } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

给定我们一个原数组 我们从数组中选择一个字符作一号位

for (size_t i = index ; i < nums.size() ; i++)
1

swap(nums[i] , nums[index]);  
1

选择完一号位之后我们再选二号位 之后依次递归即可

process(nums , index + 1 , ans);  
1

如果要求字符串不重复应该怎么做呢？

如果要求字符串不重复 这里有两种方式

1. 我们使用unordered_set容器来保存答案
2. 进行剪枝

我们可以设置一个bool数组 如果说某个元素已经做个头了 我们就不让它做头了

未剪枝前

剪枝代码

剪枝后

不申请额外的空间 逆序输出一个栈

我们现在申请一个栈 现在它内部有 1 2 3 4 5 6

如果我们正常输出 应该是这样子的

现在我们要逆序这个栈的输出 我们可以这么做

void revprint(stack<int>& st)    
{    
  if (st.empty())    
  {    
    return;    
  }    
  else    
  {    
    int top = st.top();    
    st.pop();    
    revprint(st);    
    cout << top << " ";                                                                                                         
  }    
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14

使用系统栈 等消栈的时候打印即可