Reproduced from 「 Liu Yue's technology blog 」https://v3u.cn/a_id_186
“ Never before , That's right ？”, Mr. Lu Xun is in 《 A Madman's Diary 》 By the mouth of a madman in the moonlight to question and shout , Yes , Never before , That's the way people think , Take high numbers as an example , Most of us start with a few points 、 Lineage 、 To learn functional by solving some problems 、 Generation 、 Topology, etc , In fact, we should follow the standard way , In theory, this can increase the understanding of what has been learned , And for some numbers 、 It's helpful to see the nature of the problems in line generation . Mathematical induction is actually an iteration (iteration), From a simple starting point , Generalize to the general situation . And recursion (recursion), It's an anti human reverse thinking mode , As R & D personnel , It is necessary to master this kind of logic of thinking against common sense , Here we start with a reasoning story ：
On a rainy autumn night , Japan's police department search division, police sergeant ninzaburo Hata and his assistant Jinquan driving a car on the mountain road , All of a sudden , The car broke down , In desperation , Hata had to get out of the car and walk for help , He was attracted by the light of a villa not far away , Hata knocked on the door of the villa , The one who opened the door was the beautiful cartoonist kanami , This is her private villa , It's a criminal policeman that chiennami learned , He told Hata a terrible truth , In the warehouse of her private villa , There's a body , This body is not who , It's Mr. Hatano, the editor of comic book publishing house , The dead man was lying face down on the ground , There were bruises on the body's forehead , There are papers scattered around . He just held one of the manuscripts in his hand , And there's no last words left on the paper , Just a piece of white paper , By coincidence , Next to it is a pen with its cap open , After a brief survey of the site , Hata asked about the relationship between chiennami and Hatano , Chiennami said they were just working together . But because I often come here to discuss Publishing , So she gave me a key .
And then , Chiennami explained with a smile , Mr Hatano may have died in an accident , Once the door of the warehouse is closed , It can't be opened from inside . Hatano's death may be due to carelessly locking himself in , The cause of death was asphyxia due to lack of oxygen , She has not come to the villa for more than a month , Just now , She just found Hatano's body . Hata didn't think so , He suspected it was a murder . Because the victim had a scar on his head , Bleeding . Chiennami thinks it's impossible , Because the door is closed , You can't open it without a key , Only she and Mr. Hatano have the key to the villa , No one else can come in and break Hatano's head , And I haven't been here for more than a month , Hata was suspicious , He thinks that chiennami's statement is not reasonable . It's like having a can of biscuits , When we opened it, we found that a piece of it had been bitten , Usually , We would all guess that someone bit the biscuit first and then covered it . Smart Hata finds that chiennami's words and deeds are questionable , So back to the warehouse , In the pocket of the deceased, we found several shopping receipts from three days ago , Accordingly , Gu Hata said ： The victim must have known the killer's name , Because three days ago, the dead came to the villa with the murderer , And there must be clues to the truth of the murderer hidden around the dead , Why is the dead in so many manuscripts , Hold on to this blank manuscript ？ There is a pen and paper , But nothing . What is he trying to express ？ Gu Hata thought inexplicably .
here , lighting accompanied by peals of thunder , There was a sudden blackout in the house . Chien Nai Mei couldn't help sighing ：“ Tonight? , It's terrible ！”, The night of thunder and rain 、 Deep villa 、 Beautiful girl 、 Dark warehouses and horrible bodies , All this seems so strange and mysterious , Chiennami takes out the candle , I found that Hata was reading a book , Hata kuhata praised chiennami's book as a masterpiece . Late at night , Both are hungry , They come to the storeroom , Without thinking, the woman took out her eggs and wanted to make egg soup . The careful Hata suspects that ： You haven't been here for more than a month , So are the eggs still edible here ？
Back to the villa , Gu Hata said to Qian Naimei ：“ Please forgive me for having to tell the truth , Three days ago , It's the villa that miss kanami and Mr. Hatano came to together ？”,“ The last time I came here was a month ago ,”, Chiennami's face is expressionless ,“ You're not telling the truth . How do you know if the eggs in the refrigerator are fresh ？ The last time you came here was not a month ago , So you put your eggs in the fridge three days ago . In my imagination , Beautiful cartoonists and Playboy editors who don't know the world , I don't know what happened between you , But one of them finally found out that the other was just playing on the spot , So there was a cruel revenge .”,“ Mr. Hata , It's really a conventional story ”, Chiennami smiles ,“ Why did the killer break the head of the dead man ？ If people think it's an accident , The killer would never do that . Am I right? ？ But the victim was wounded , This is contradictory . So I thought it over , Is it possible that the person who disguises murder as an accident is not the same person as the one who deliberately leaves evidence of homicide ？”,
“ Are there two murderers ？”,“ There's only one killer , In fact, we have overlooked a very important point , This is the white paper , The dead did leave a trail , It's just that we haven't found out yet . The clues are left on this piece of paper . Let's transpose and think about , Imagine how Hatano felt at that time , He wanted to leave the killer's name anyway , But no matter how he tries to write down the killer's name , If the killer finds out first , Will be destroyed , He was very clear about that , It must have been the killer who found the body first , Because the killer kept him in the warehouse , So? , He thought about it , First pick up a piece of paper , Take off the cap , And it's nothing , Do you understand ？ If you can write down the killer's name , He didn't write anything , That's what he left behind . What he's trying to convey is ‘ Whatever I write is useless ’”.
“ What about the wound on his head ？ How to explain ？“
“ This is one of the clues Mr Hatano left behind . Because no matter how he tries to leave a clue , If the case is handled as an accident , So it doesn't make sense . So he's going to leave it anyway. It's evidence of homicide , therefore , He gave his head a shot himself .”
Yes , A blank sheet of paper with nothing written is a clue left by the dead . This piece of white paper is telling in silence ： My killer , The first person to find my body .
The story itself is not complicated , Love begets hate in dog blood murder , But the core of the story is a piece of white paper , The only clue left by the dead , This clue was discovered by Hata , It's not that the dead don't want to name the killer , It's not saying , What Hata uses here is actually recursive logic based on reverse thinking .
that , At the code level , What problem can recursion help us solve ？ Let's take Gauss summation as an example , So called Gauss summation , That is, within a threshold range , The arithmetic problem of summing all integers , If you use iterative logic ：
def sum_number(n): total = 0 for i in range(1, n+1): total += i return total
Calling method ：
print(sum_number(5)) liuyue:mytornado liuyue$ python3 "/Users/liuyue/wodfan/work/mytornado/excel_test.py" 1 3 6 10 15 15 liuyue:mytornado liuyue$
You can see , The essence of iterative thinking is incremental traversal , Add elements one by one in order , It's not hard to understand , Now let's try recursion ：
def sum_number(n): if n <= 0: return 0 return n+sum_number(n-1)
You can see , When we use recursion to design programs , We start with the end result , That is, in order to get sum\_number(5), The computer will break this calculation down to get sum\_number(4) Arithmetic , as well as sum\_number(4) add 5 Arithmetic . And so on , Until it's broken down into sum\_number(1) Arithmetic , Trigger the termination condition , That is to say if In structure n<=0 when , Returns a specific number 0. Although the whole recursive process is very complicated , But in programming , We just need to focus on the initial conditions 、 Termination conditions and convergence , Instead of focusing on every specific step .
Recursive thinking is from the top down , When we do things, we can consider the whole first . First, define the big goals that need to be achieved , It's not to start with the details , This is also the thought of system theory . A lot of new programmers , In the absence of a clear overall functional architecture of the project , Just in a hurry to write code , In the end, it often leads to multiple rework , The wasted effort , But the use of Python When designing recursive programs, we need to pay attention to the problem of stack overflow , If the recursion depth exceeds 1000 You'll report an error , So you need to set the recursion depth separately ：
import sys # Change the recursion depth to 1 One million sys.setrecursionlimit(1000000)
Find out the simple idea of recursion , Let's try the advanced operation ： Tail recursion . Tail recursion is relative to traditional recursion , It's a special case . In tail recursion , Perform some part of the calculation first , Then start calling recursion , So you can get the current results , And this result will be passed into the next recursion as a parameter . This means that the function call appears at the end of the caller's function , Because it's the tail , So it has an advantage over traditional recursion in that it doesn't need to save any local variables , In terms of memory consumption , Realize the saving feature ：
def tail_sum(n,result=0): if n==0: return result else: return tail_sum(n-1, result+n)
The traditional recursive solution steps ：
5+sum_number(4) 5+(4+sum_number(3)) 5+(4+(3+sum_number(2))) 5+(4+(3+(2+sum_number(1)))) 5+(4+(3+(2+1))) 15
Every recursion , The program stores the results in memory , Do accumulation in recursion , Until we go to the recursive exit , Tail recursion is to recursively pass the accumulated results through the reference ：
tail_sum(5,0) tail_sum(4,5) tail_sum(3,9) tail_sum(2,12) tail_sum(1,14) tail_sum(0,15)
If the recursion depth is very large , You can save a lot of memory costs .
Related video introduction , Please move ：
Sum up , Skilled use of recursion need to pay attention to the following three characteristics ：
1. The problem itself can be split into simpler subproblems , And subproblems can be solved in the same way .
2. To solve the problem, you need to consider the program exit in advance , Otherwise, you will fall into the trap of recursive loop .
3. Recursion is not a very efficient algorithm , Large scale problems need tail recursion .
Conclusion ： People who master recursive reverse thinking , In solving some tough problems , It's often possible to find another way , Good at using resources , Find a clever way to solve the problem , Just like the criminal police of Hata at the beginning of the article . When we face life 、 Social problems , Can you imagine Mr. Lu Xun's sentence “ Never before , That's right ” The cry of .“ Never before ” Maybe it is , Maybe not . But as a contemporary , Introspection , Let me share with you .
Reproduced from 「 Liu Yue's technology blog 」 https://v3u.cn/a_id_186