Some classic recursion problems

There are two factors that must be considered when writing recursive problems ： Recursive termination condition and iteration condition

The hanotta problem

Problem description

Now there are three pillars , Number A,B,C. Now there is n Disc , The specified disc can only Put the small disc on the big disc （ Don't put the big disc on the small disc ）, initial n All the discs are A On the column , Now we have to put A All the discs of move in C On

Please return to your moving steps , Minimize the number of moves

Thinking solution

This problem may be difficult for us to achieve for a while , We can decompose the sub problem

Just imagine ： If we want to put 2 What steps are needed to move a disc ？

• Move the upper one to the middle
• Move the last one to the target
• Move the middle disc to the target

In this case , We can promote ：

If we had n A disc ：

• Top up n-1 A disc moves to the middle
• Move the last disc to the target
• Put in the middle of the n-1 A disc moves to the target

Just like this. ：

Then for the above n-1 The disk of , We can consider from n-2 To n-1 Call this procedure repeatedly

This is our optimal solution

So our initial function may need the following process

if(n==1)
{
    
	A->C;// In the case of only one disc 
}

fromAToB(n-1);// Top up n-1 A function with a disk in the middle 
A->C;// Put the last disk of the current disk stack at the target 
fromBToC(n-1);// Put all the discs in the middle at the target 
}

For the two functions in the procedure , You can think of them as black boxes for the time being , They only perform the movement process

Because our main process is from A To C, So our main function is fromAToC(n)

As for the functions involved in our middle , We can imitate our thoughts , Make it up easily

for example fromAtoB

if(n==1)
{
    
	A->B;// In the case of only one disc 
}

fromAToC(n-1);// Top up n-1 The discs are stored in C
A->B;// Put the last disk of the current disk stack at the target 
fromCToB(n-1);// Put the middle disc back on the target 

By analogy , We have written the solution of six function interdependence

	void hanoiTest2(int n)
	{
    
		fromAToC(n);// Our main process 

	}
	void fromAToB(int n)
	{
    
		if (n == 1)
		{
    
			cout << "1 Number ：" << "A->B" << endl;
			return;
		}
		fromAToC(n - 1);
		cout << n << " Number ：" << "A->B" << endl;
		fromCToB(n - 1);
	}

	void fromAToC(int n)
	{
    
		if (n == 1)
		{
    
			cout << "1 Number ：" << "A->C" << endl;
			return;
		}
		fromAToB(n - 1);
		cout << n << " Number ：" << "A->C" << endl;
		fromBToC(n - 1);
	}

	void fromBToC(int n)
	{
    
		if (n == 1)
		{
    
			cout << "1 Number ：" << "B->C" << endl;
			return;
		}
		fromBToA(n - 1);
		cout << n << " Number ：" << "B->C" << endl;
		fromAToC(n - 1);
	}

	void fromBToA(int n)
	{
    
		if (n == 1)
		{
    
			cout << "1 Number ：" << "B->A" << endl;
			return;
		}
		fromBToC(n - 1);
		cout << n << " Number ：" << "B->A" << endl;
		fromCToA(n - 1);
	}

	void fromCToA(int n)
	{
    
		if (n == 1)
		{
    
			cout << "1 Number ：" << "C->A" << endl;
			return;
		}
		fromCToB(n - 1);
		cout << n << " Number ：" << "C->A" << endl;
		fromBToA(n - 1);
	}

	void fromCToB(int n)
	{
    
		if (n == 1)
		{
    
			cout << "1 Number ：" << "C->B" << endl;
			return;
		}
		fromCToA(n - 1);
		cout << n << " Number ：" << "C->B" << endl;
		fromAToB(n - 1);
	}

How can we change the above function into a recursive version ？

Let our three pillars be from,other,to
among from Represents the starting position of the disc ,to Represents the target location we are moving ,other Represents another auxiliary location

Our goal is to from All discs of move to to

Let's change the three processes of the above function

fromAToC(n-1);// Top up n-1 The discs are stored in C
A->B;// Put the last disk of the current disk stack at the target 
fromCToB(n-1);// Put the middle disc back on the target 

First process , We first put the top n-1 The discs move to the auxiliary position , It is convenient for our largest disc to move
So our first process aims at the above n-1 Disc , The goal has been changed to other, utilize to Move them to other

Second process , We take the largest disc from from Move to to

The third process , We need to return , That is, turn the middle disc from other Move to to, The auxiliary position is from

Let's talk about it n-1 A place , Repeat the process , You can decompose the big problem

	void hanoiTest1(int n,string from, string to, string other)
	{
    
		if (n == 1)
		{
    
			cout << n<<" Plate No :"<<from << "->" << to <<endl;
			return;
		}

		hanoiTest1(n - 1, from, other, to);// First step ,n-1 from from To other
		cout << n << " Plate No :" << from << "->" << to <<endl;// The second step ,n Oneself from from To to

		hanoiTest1(n - 1, other, to, from);// The third step ,n-1 from other To to
	}

Come down and test our two problems

You can test the correctness of our answers through this website http://www.7k7k.com/swf/201271.htm

Substring problem

Problem description ：

Give you an arbitrary string , Output all its subsequences

for example ：“abc”

Output ：“a”,“b”,“c”,“ab”,“ac”,“bc”,“abc”

Thinking solution ：

Our problem , In fact, it can be decomposed into two situations Select a character , Or not

We can traverse each string , Divided into them , Or not choose these two cases to judge , Until all characters are judged , Then make a retrospective judgment

Just like this. ：

All we need are the following parameters

Return value array vector, When we use recursion , If you need to record your answers , It's best to use it as a reference parameter

Subscript index, Judge whether the characters in the string have been judged

character string path, Record the current selection method

And our original array

The code is as follows , See the notes for details

	vector<string>PrintAllSubsquences(string s)
	{
    
		int index = 0;
		string path = "";
		vector<string>ans;
		_PrintAllSubsquences(s, index, path, ans);
		return ans;
	}
	void _PrintAllSubsquences(string s, int index, string path, vector<string>&ans)
	{
    
		if (index == s.size())// The string is judged 
		{
    
			ans.push_back(path);
			return;
		}

		_PrintAllSubsquences(s, index + 1, path, ans);// The current character is not selected , Continue to judge 
		_PrintAllSubsquences(s, index + 1, path+s[index], ans);// Current character selection , Continue to recurse down 
	}

In the above code, we may encounter the problem of repeated substrings , For example, we need to ask "accc" The string of

There's a lot of repetition

To avoid this problem , When we accept the answer, we'd better use Hash set （unordered_set） This container

String Full Permutation

Problem description ：

Give you a string , Find all permutations of strings

for example ：“abc”

Output ：“abc”,“acb”,“bac”,“bca”,“cab”,“cba”

Thinking solution ：

We can use the original string , Just exchange

for example ： our 0 Position and 0 Location switching , It means that we will not exchange characters this time

We 0 and 1 Location switching , Formed "bac" This string

We can traverse every character , Then try to exchange it with each character

So we can write the following code

	void _PrintAllPermutations(string s, int index, vector<string>& ans)
	{
    
		if (index == s.size())
		{
    
			ans.push_back(s);// The character traversal is finished , Return the exchanged string 
			return;
		}
		for (int i = index; i < s.size(); i++)
		{
    
			Swap(s, index, i);
			_PrintAllPermutations(s, index + 1, ans);// Traverse all exchange selections for the next location 
			
		}
	}

But this code is wrong

We are in the process of recursive backtracking , Usually Restore the scene

Because after we exchange on this layer , Go back to the previous function , Take it The exchanged strings are sorted , The answer is ultimately incorrect

So we need to finish every recursion , Restore the scene

	void _PrintAllPermutations(string s, int index, vector<string>& ans)
	{
    
		if (index == s.size())
		{
    
			ans.push_back(s);// The character traversal is finished , Return the exchanged string 
			return;
		}
		for (int i = index; i < s.size(); i++)
		{
    
			Swap(s, index, i);
			_PrintAllPermutations(s, index + 1, ans);// Traverse all exchange selections for the next location 
			Swap(s, index, i);// Restore the scene 
		}
	}

Our code can also perform a de duplication optimization

Set up a bool used[128] Array of , Record the character of the operation if a character does not appear , To operate

The complete code is as follows

	vector<string>PrintAllPermutations(string s)
	{
    
		int index = 0;
		vector<string>ans;
		_PrintAllPermutations(s, index, ans);
		return ans;
	}
	void _PrintAllPermutations(string s, int index, vector<string>& ans)
	{
    
		if (index == s.size())
		{
    
			ans.push_back(s);
			return;
		}

		bool isUsed[128] = {
     0 };
		for (int i = index; i < s.size(); i++)
		{
    

			if (!isUsed[(int)s[i]])
			{
    
				isUsed[(int)s[i]] = true;
				Swap(s, index, i);
				_PrintAllPermutations(s, index + 1, ans);
				Swap(s, index, i);
			}
		}
	}

	void Swap(string& s, int x, int y)
	{
    
		char tmp = s[x];
		s[x] = s[y];
		s[y] = tmp;
	}

Reverse order stack

Problem description ：

Give you a stack , requirement Only recursion... Can be used , And can't open up additional data structures , Reverse this stack

Thinking solution ：

If we want to reverse the stack , First of all, we must find a way to get the elements at the bottom of the stack , The elements need to be pushed back to the bottom of the stack in the original order

For example, we have this stack

We need a function , It doesn't affect 2,3 The order of things , take out 1

We can do this ：

Take out an element first , Then judge whether it is empty

Empty to return directly to There is only one element in the current stack , The top, of course, is itself

Then we recurse like this The bottom of the function stack keeps returning the answer up

So we recursively get the code at the bottom of the stack as follows

	int f(stack<int>& s)
	{
    
		int result = s.top();// Get to the current top 
		s.pop();
		if (s.empty())
		{
    
			return result;
		}
		else
		{
    
			int last = f(s);// Keep going down , You can get the bottom 
			s.push(result);// The current function stack frame records the value , You can put it down directly 
			return last;// Keep returning the bottom up 
		}

	}

In our main function , You need to keep taking out the bottom of the stack , Record the obtained value in each stack frame , Then return in turn

	void reverseStack(stack<int>& s)
	{
    
		if (s.empty())
		{
    
			return;
		}

		int i = f(s);// Take out the last one , And put the above elements again according to the original sequence 
		reverseStack(s);
		s.push(i);
	}