当前位置:网站首页>The ingenious understanding of recursive thought
The ingenious understanding of recursive thought
2020-11-06 01:35:38 【itread01】
Logic is the age of mathematics , Mathematics is the age of logic .
—— Russell
“ Recursion ”
This is in the program 、 The foundation and top priority in algorithm design . It took me a lot of time to understand this , For beginners , How to show a process vividly , Became the key to understanding this idea .
The reason for this blog post , From a question my classmate asked me :
I'll see it , This wave , This wave is obviously going back !!
I thought , How to explain , Is to open Baidu search to return :
Define
The programming technique of calling itself is called recursion ( recursion). Recursion as an algorithm is widely used in programming languages . A procedure or function has a way of calling itself directly or indirectly in its definition or description , It usually transforms a large and complex problem into a smaller problem similar to the original problem to solve , The recursive strategy only needs a few programs to describe the repeated calculation needed in the process of solving problems , It greatly reduces the amount of code in the program . Recursion is the ability to define an infinite set of objects with finite statements . In general , Recursion requires boundary conditions 、 Step forward and step back . When the boundary conditions are not satisfied , Go back and forth ; When the boundary conditions are satisfied , To return to .
I think this , That's such a tough explanation , Let's not bother people , So this explanation has been pigeon for several days
ideas
One night of fish fishing , I suddenly came up with a vivid example of interpretation recursion , That's it :
Russian Dolls !!
So , How to use the idea of Russian dolls to understand the idea of recursion ?
And it's known to all , Recursion is actually a program calling itself , It's not like , I have a self in my stomach ?
But , The way we open this set of Dolls , You have to follow the following rules ;
Take the top half of the dolls first ( The code above the function that executes the call itself );
Keep taking the upper half , Until I took out a baby that couldn't be opened ( Go back to the end );
Look at this baby who can't have a baby again ( Complete execution of this most “ deep ” Function of );
Take out the lower body of all dolls in turn ( Execute the bottom half of all recursive functions from the bottom up ).
Case interpretation
Let's take a look at the code to find the depth of the tree :
int TreeDepth(BT *T){ int ld=0,rd=0; if(T==NULL) return 0; else{ ld=TreeDepth(T->lchild); rd=TreeDepth(T->rchild); if(ld>rd) return ld+1; else return rd+1; } }
I'll draw a picture and see
Suppose there is such a tree ,BT Is the index in the function *T The position of
We run this code
int TreeDepth(BT *T){ int ld=0,rd=0; if(T==NULL) return 0; else{ ld=TreeDepth(T->lchild);
First, return to the bottom , Walking down , Is full of NULL 了 , You can run the next section of code
if(ld>rd) return ld+1; else return rd+1;
Of course , Here ld and rd All are 0, The return value is 1, According to
ld=TreeDepth(T->lchild);
And the last level of function ld=1
Let's continue to see , Because the execution of this function has ended , Let's run the second half of the code from the previous function .
rd=TreeDepth(T->rchild); if(ld>rd) return ld+1; else return rd+1; } }
Here we find , You can go all the way down the right tree , Refer to the previous step , And so on , We get the following figure
And push on , The return value of the whole program is clear at a glance
I'd like to talk about depth first search again (DFS), As we all know, the most basic skill of deep search is recursion .
PS: Although deep search can also be achieved by stack , But recursion means that the program calls up the stack to store data , There is little difference .
Trees are special graphs , The traversal of the tree is also the graph traversal , This way of traversing the depth in one breath , It's what we call DFS, In the process of learning the foundation of tree , We can also experience many properties of graphs
I hope that my proposal can cause more thinking
版权声明
本文为[itread01]所创,转载请带上原文链接,感谢
边栏推荐
- C++ 数字、string和char*的转换
- C++学习——centos7上部署C++开发环境
- C++学习——一步步学会写Makefile
- C++学习——临时对象的产生与优化
- C++学习——对象的引用的用法
- C++编程经验(6):使用C++风格的类型转换
- Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
- C + + number, string and char * conversion
- C + + Learning -- capacity() and resize() in C + +
- C + + Learning -- about code performance optimization
猜你喜欢
-
C + + programming experience (6): using C + + style type conversion
-
Latest party and government work report ppt - Park ppt
-
在线身份证号码提取生日工具
-
Online ID number extraction birthday tool
-
️野指针?悬空指针?️ 一文带你搞懂!
-
Field pointer? Dangling pointer? This article will help you understand!
-
HCNA Routing&Switching之GVRP
-
GVRP of hcna Routing & Switching
-
Seq2Seq实现闲聊机器人
-
【闲聊机器人】seq2seq模型的原理
随机推荐
- LeetCode 91. 解码方法
- Seq2seq implements chat robot
- [chat robot] principle of seq2seq model
- Leetcode 91. Decoding method
- HCNA Routing&Switching之GVRP
- GVRP of hcna Routing & Switching
- HDU7016 Random Walk 2
- [Code+#1]Yazid 的新生舞会
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- HDU7016 Random Walk 2
- [code + 1] Yazid's freshman ball
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- Qt Creator 自动补齐变慢的解决
- HALCON 20.11:如何处理标定助手品质问题
- HALCON 20.11:标定助手使用注意事项
- Solution of QT creator's automatic replenishment slowing down
- Halcon 20.11: how to deal with the quality problem of calibration assistant
- Halcon 20.11: precautions for use of calibration assistant
- “十大科学技术问题”揭晓!|青年科学家50²论坛
- "Top ten scientific and technological issues" announced| Young scientists 50 ² forum
- 求反转链表
- Reverse linked list
- js的数据类型
- JS data type
- 记一次文件读写遇到的bug
- Remember the bug encountered in reading and writing a file
- 单例模式
- Singleton mode
- 在这个 N 多编程语言争霸的世界,C++ 究竟还有没有未来?
- In this world of N programming languages, is there a future for C + +?
- es6模板字符
- js Promise
- js 数组方法 回顾
- ES6 template characters
- js Promise
- JS array method review
- 【Golang】️走进 Go 语言️ 第一课 Hello World
- [golang] go into go language lesson 1 Hello World