Understanding recursion with examples

Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>

---

0. What is recursion

       Before you say what recursion is , I think you should be able to use loops to solve some problems in reading . What is that cycle ？ Loop is a program structure that needs to perform a function repeatedly in a program . It is by the conditions in the circulatory body , Determine whether to continue a function or exit the loop .

       for example ：1+2+3+4+……+10 How much ?（ We exclude mathematical formulas ）

The first solution is to use loops to solve .

The second solution is to use recursion .

       You can see , A loop is the repeated execution of code within a certain region , Until the termination conditions are met , If not controlled , And it will form a cycle of death . And recursion is calling itself in function body , While using recursion , Be sure to pay attention to the end conditions , If not controlled , Will call yourself endlessly , Until the stack overflows back , Because every time a function is called, it creates a stack frame on the stack , The stack frame will pop up after the function call , And the stack size is not infinite , So too many recursive calls will lead to stack overflow . And the characteristic of recursive call is every recursion , To create a new stack frame , And keep the previous environment （ Stack frame ）, Until the end condition . So recursive calls must be clear about the end conditions , Don't have a dead cycle , And avoid the stack being too deep ..

       If you go to the advantages and disadvantages of Baidu loop and recursion , There may be such an answer ：

A recursive algorithm ：
advantage ： The code is concise 、 Clear , And it's easy to verify the correctness .（ If you really understand the algorithm , Or you'll be more dizzy ）
shortcoming ： It needs more function calls to run , If the call level is deep , Need to add extra stack handling , For example, parameter transfer requires stack pressing and other operations , It will have a certain impact on the efficiency of implementation . however , For some problems , If you don't use recursion , That would be extremely ugly code .
Loop algorithm ：
advantage ： Fast , Simple structure .
shortcoming ： It doesn't solve all the problems . Some problems are suitable for recursion instead of loops . If it's not difficult to use a loop , It's better to use cycle .

       I think the advantages and disadvantages are summed up in a lot of contact with loops and recursion , For us this little white , Basically, there is no need to tangle , We can't understand , So let's not think about it for the moment , As it says , If you really understand the algorithm , Or you'll be more dizzy .

       Let's go on to see , For the top 1+2+3+4+……+10 The simple question of how much is equal to , Loop and recursion can solve , And recursion doesn't show the simplicity of its code , Clear . So I don't think we can compare loops with recursion , Take the sequential structure , Branching structure , Loop structure , Modular structure , For these four structures , Loop has always been a basic content , Recursion is an algorithm for solving specific problems , It's also a kind of cycle in essence , For the above questions , The advantages of recursive algorithms are not obvious , It's a little skeptical , So when you solve a problem , It depends on the complexity of the problem , According to the complexity of the problem, different algorithms are adopted , Rather than say , I learned recursion , I should use it , Because the book says its code is concise .

And then I want to use recursion , The most important tip , Remember ：

• Make sure that this recursive function works （ No specific code is required ）
• Find recursive end condition
• Find the equivalent relation or the least recursive model of the function
• Don't try to track recursive processes

---

The following through the use of pithy formula to solve the problem from easy to difficult to understand recursion ：

1. Fibonard sequence

The Fibonacci sequence refers to a sequence that looks like this ：

This sequence starts at number one 3 A start , Each of these terms is equal to the sum of the first two terms , This is also a common problem in recursion .

First step ：
Make sure that this recursive function works , What does this function do ？ That's the output number n Item value .

int fun(int n)
{
   
     

}

The second step ：
Find recursive end condition , When n Less than or equal to 1 perhaps 2 When , It's time to end recursion .

int fun(int n)
{
   
     
	if(n<=2)
	{
   
     
		return 1;
	}
}

The third step ：
Find the equivalent relation of function , It is shown in the preceding paragraph that the sequence starts from 3 A start , Each of these terms is equal to the sum of the first two terms , That is to say f(n)=f(n-1)+f(fn-2).

int fun(int n)
{
   
     
	if(n<=2)
	{
   
     
		return 1;
	}
	return fun(n-1)+fun(n-2);
}

---

2. The little frog went up the steps

A frog can jump up at a time 1 Stepped steps , You can jump on it 2 level , Ask the frog to jump on one n How many jumps are there in total .
First step , It is true that recursive functions act , seek n How many kinds of jump methods are there in the steps of the steps .
The second step , Indeed, the end condition , When the step equals 0,1,2, There were 0,1,2 Methods , We can sort this out .

int fun(int n)
{
   
      
	if(n<=2)
	{
   
      
		return n;
	}
}

The third step , Determine the equivalent relation , When there is n Steps , Select jump 1 rank , That's all fun(n-1) Methods , Select jump 2 rank , That's all fun(n-2) Methods . The sum of the two methods is the total .

int fun(int n)
{
   
      
	if(n<=2)
	{
   
      
		return n;
	}
	return fun(n-1)+fun(n-2);
}

---

3. Hantata

       The more famous is hannota （ Also known as the river tower ） problem , Hanoi Tower originated from an ancient legend in India . Vatican made three diamond pillars when he created the world , Stack on a column from bottom to top in order of size 64 A golden disk . Brahman ordered Brahman to rearrange the disc from below on another pillar in order of size . And stipulate , You can't enlarge a disc on a small disc , Only one disc can be moved between the three pillars at a time , And it must be the top disk , This question is still difficult , Let's analyze the problem .

A Column as source ,B Columns as auxiliary columns ,C Column as target pillar .
set up N Count the sets , When N be equal to 1 when , Just one step ：A——C Here's the picture ：

set up N Count the sets , When N be equal to 2 when , It takes three steps ：A——B,A——C,B——C Here's the picture ：

set up N Count the sets , When N be equal to 3 when , need 7 Step ：A——C,A——B,C——B,A——C,B——A,B——C,C——A Here's the picture ：

When N As we grow older , More and more steps are needed , When N be equal to 64, If you move correctly once a second , It also takes 5845.42 More than one hundred million , And the earth still exists 45 In one hundred million, , This number is too large ！ So about recursion , We must not track the process of large recursion , The key is to find the minimum recursion model or the equivalent relation of recursion mentioned above .

First step , We're going to show the message in a black box , Step several which plate moves from which pillar to which post .
This print function needs 4 Parameters and a global variable are used to output the number of steps .

void move(int id, char form, char to)
{
   
       
	cout << " The first " << sum++ << " Step ： take " << id << " Plate from " << form << " Move to " << to<<endl;
}

And determine the purpose of the function ： Output step which plate moved from which column to which column , We use move Function to output .

The second step , Find the recursive end condition , When n be equal to 0 Or 1（ Another way of writing , I didn't write ）, As an end condition .

The third step , It's the search for the minimal recursive model .
We have three pillars and n null , So the definition of a function should be ：void fun(int n, char a, char b, char c),a,b,c Three columns are corresponding respectively . We're looking for a minimal recursive model ：fun(n) The previous step fun(n-1) How can we go there? . When n be equal to 1 when , Directly from the plate A The column moved to B Just a column , When n be equal to 2 when , Pictured above , It takes three steps , It's also the minimal recursive model we're looking for , When n=2 when
fun(n - 1, a, c, b); Denotes marked as n-1 disc , from A The column passes through the auxiliary column C Move to B column
move(n, a, c); Indicates marked as n Disk , from A The column moves to C column
fun(n - 1, b, a, c); Denotes marked as n-1 disc , from B The column passes through the auxiliary column A Move to C column

take n-1 As a whole ,n and n-1 Just the three fixed steps , The complete code is as follows ：

int sum=1;    // Record the steps 
void move(int id, char form, char to)
{
   
       
	cout << " The first " << sum++ << " Step ： take " << id << " Plate from " << form << " Move to " << to<<endl;
}
void fun(int n, char a, char b, char c)
{
   
       
	if (n == 0)return; 
	fun(n - 1, a, c, b);
	move(n, a, c);
	fun(n - 1, b, a, c);
}
int main(int argc, char** argv) {
   
       
	while (1)
	{
   
       
		sum = 0;
		int x;
		cin >> x;
		fun(x, 'A', 'B', 'C');
	}
	return 0;
}
}

Here are examples , Study slowly , You will find that recursion is a magic thing , I can be understood by an average person like me , I think you all understand , And learning recursion also has to mention a term called iteration , About iteration , Later on .

---