Table of Contents
recursive review
From recursion to stack overflow
Problem introduction
special perspective
Problem regression
problem solved
subprocess
Computer memory (why stack overflow occurs)
What is stack overflow
summary
Recursive review
Recursion of functions [frog jumping up stairs]
https://mp.csdn.net/mp_blog/creation/editor/133971224
Text
I believe that when you write function recursion, you will definitely try the simplest recursion, but in fact it is not the correct way to write recursion:
e.g.1
#include<stdio.h>
int main()
{
printf("hehe\
");
main();
return 0;
}
You will find:
After the program enters from the main() function, it will call the main() function again, seemingly never stopping;
result:
The program eventually crashed, but what caused the crash?
If you press F10 to debug, you will find a detailed error message:
The error message is: stack overflow!
From recursion to stack overflow
Hanoi Tower
I believe you must know the problem with the Tower of Hanoi:
When Brahma created the world, he made three diamond pillars. On one pillar, 64 gold discs were stacked in order of size from bottom to top. Brahma ordered the Brahmin to rearrange the disks on another pillar in order of size from the bottom. It is also stipulated that the disk cannot be enlarged on the small disk, and only one disk can be moved between the three pillars at a time.
Special perspective
Let’s start with a simple case:
?
When moving 4 pieces, there will be a state during the movement. In this state:
1. The bottom plate No. 4 is placed on the target pillar; (the status of other plates is not so important)
2. The other plates are placed on the first pillar from top to bottom, from small to large; (this must be done in order to continue the game)
At this point, we have finished moving the bottom plate.
So, the status of the plate at this time:
?
At this time:
You will find that the next step is to move the three-layer plate. I believe this is not a problem for you.
Problem regression
When we try to move n plates from “start” to “dest”:
1. The above (n-1) plates can be regarded as a whole,
2. The bottom plate: The nth plate is regarded as an individual with the same status as the whole;
Therefore, our goal of moving n plates from “start” to “dest” can be decomposed into:
First move the top (n-1) plates to “dest”, and then move the nth plate to “dest”.
However, our power is limited and we can only move one plate at a time. Therefore, we can use the above method again;
First move the top (n-2) plates to “dest”, and then move the (n-1)th plate to “dest”.
…
Problem Solving
Here, for the convenience of expression, I introduce the concept of “n-reducing program”:
Each time the n-reducing program is executed, the number of remaining plates that need to be moved will be reduced by 1;
And every time the “n-drop program” is executed, the (n-1) plates above must be moved twice;
Under the premise that only one plate can be moved at a time, we call the operation of moving n plates “moving n operation”; 
Just imagine:
In the case where the (n-1) plates above are not equal to 1, since we can only move one plate at a time, so – every time we move the (n-1) plates above, we must first move the (n-1) plates above n-2) plate, and the (n-1)th plate.
That is to say:
1. One “move n program” includes two “move n operations”;
2. “The move n operation can be completed when and only when n = 1;
So, the number of times required to move n plates is: 2^n – 1 times! (Why “-1”? – Because when n = 1, the movement can be completed in one go, without further division)
Subprocess
When you look back at the Tower of Hanoi problem, you will find that:
If we want to move n plates to the destination, we must first move the upper (n-1) plates, and to move the upper (n-1) plates, we must first move the upper (n-2) plates…. ..
In other words, if the (n-2)th plate has not completed its movement, then the second “n-drop procedure” has not been completed! If the (n-3)th plate has not completed its movement, then the third “n-drop procedure” has not been completed!
……
In other words, the deeper level of recursion is a sub-process of the current level of recursion!
What if this process happened in the computer’s memory?
Each recursion will open up a new space in the stack area of the memory.
It’s easy to find the reason.
Computer memory (why stack overflow occurs)
In fact, the computer’s memory can be divided into three areas: stack area, heap area, and static area.
They follow different rules when it comes to storage usage, and what they store is also different.
As shown in the picture:
Every time we recurse, the last recursive program has not yet ended, that is, the last recursive function still occupies the space in the memory stack area;
When we call a function recursively without a breakout condition (that is, the case of e.g.1), the stack will overflow.
So, when we understand the principle of stack overflow, we will find:
Recursion that is too deep can also cause stack overflow.
e.g.2
#include<stdio.h>
void conduct(int n)
{
if (n < 10000)
{
conduct(n + 1);
}
}
int main()
{
conduct(1);
return 0;
}
Since the conduct() function called last time does not end during each recursion, the conduct() function called last time still occupies space in the stack area of the memory.
Program execution result:
Still causing stack overflow, it can be seen that when the degree of recursion is too deep, it will also cause stack overflow.
What is stack overflow
The main cause of stack overflow is that the program accesses an illegal memory address, causing data that exceeds the size of the stack space to be written, thereby overwriting data such as return addresses, parameters, and local variables of other variables or functions in the stack.
Summary
1. Stack overflow is caused by the improper use of the memory stack area;
2. When writing recursive functions, avoid dead recursion;
3. If the recursion is too deep, it will also cause stack overflow;
I hope this article is helpful.
End
Reprinting without the author’s consent is prohibited