Article Description
1
What can you learn
Learn what recursion is, what makes recursion special, how to write recursion, and how to practice common recursive problem analysis and solution.
2
The article structure
This article adopts the idea of what, why and how to do, abstracts the theory from the example, explains the example from the theory, and finally starts to practice, deepens the understanding and cognition.
Two meet recursion ~ from shy to hold hands
First encounter recursion — basic concepts
Recursion, according to MDN, is a function that calls its own operation. Used to deal with problems that contain a smaller class of subproblems.
1. For example:
Example 1:
Once upon a time there was a mountain, and there was a temple on the mountain, and there was an old monk and a young monk in the temple, and the old monk was telling a story to the young monk, and the story was as follows: Once upon a time there was a mountain, there was a temple on the mountain, there was an old monk and a young monk in the temple, the old monk was telling a story to the young monk, which was:…
<p> Not specific enough? </p> <p> </p> <p> <br/> </p> <p> <img src="//p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/50f9b3522fe0450383cecc173afbc1e9~tplv-k3u1fbpfcp-zoom-1.image" Data-ratio ="1" Alt =" recurrence. JPG "data-w="1" style="width:auto;" /> </p> <p> </p> </section> </section> <section class="box-edit"> <section style="text-align: left; margin-top:10px;" > <section style="display: inline-block; background-color: #ff8124; padding: 4px 10px; background-image: linear-gradient(116deg, #89f7fe, #66a6ff); color: #ffffff;" ><h4 style="display:flex; justify-content: center;" > <section class="autonum" style="width:25px; height:25px; background-color: #fff; color:#333; text-align: center; line-height:24px; font-size:20px; border-radius:100%;" data-original-title="" title=""> 2 </section> <section class="135brush" data-brushtype="text" style="text-align: center; line-height:24px; font-size:16px; Letter - spacing: 1.5 px; margin-left:6px;" <br/> </section> </h4> </section> </section> </section> <section data-autoskip="1" class="135brush" style="font-size:14px; Letter - spacing: 1.5 px; text-align:justify; The line - height: 1.75 em. padding:1em 0em; color: #333;" > <p> 1) Big problems can be transformed into smaller similar problems, and the way to solve big problems is the same as the way to solve small problems; </p> <p> 2) The smallest repeating unit can always be found in the big problem. Within each repeating unit, the operating environment is independent of the other units. </p> </section> </section> </section> </section>Copy the code
3
Learn more — How to write recursion
Recursion is written with a fixed template, which can be divided into four modules: the first, the end condition of recursion; The second block is the logical processing of the current layer. The third part, how to deal with the sub-module; The fourth block, the current layer needs to clean up the logic. But usually, we return at the third level.
</p>
<p>
先举个简单的例子：数组的快速排序
</p>
<p>
<img src="//p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/6008f71f2425469c815a716761c976c0~tplv-k3u1fbpfcp-zoom-1.image" data-ratio="1" alt="快速排序.JPG" data-w="1" style="width:auto;"/>
</p>
<p>
执行结果：
</p>
<p>
<img src="//p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/caad5d8ee69e4f389b31e11851e25ed3~tplv-k3u1fbpfcp-zoom-1.image" data-ratio="1" alt="捕获.JPG" data-w="1" style="width:auto;"/>
</p>
<p>
小结：
</p>
<p>
凡是递归，均可以按照上述模板思路编写代码，尤为强调的是，一定要先想好递归的退出条件，否则极有可能写出“死递归”。<br/>
</p>
</section>
</section>
<section class="box-edit">
<section style="text-align: left;margin-top:10px;">
<section style="display: inline-block; background-color: #d9f2f0; padding: 4px 10px; background-image: linear-gradient(116deg, #89f7fe, #66a6ff); color: #ffffff;">
<h4 style="display:flex;justify-content: center;">
<section class="autonum" style="width:25px;height:25px;background-color: #fff;color:#333;text-align: center;line-height:24px;font-size:20px;border-radius:100%;" data-original-title="" title="">
4
</section>
<section class="135brush" data-brushtype="text" style="text-align: center;line-height:24px;font-size:16px;letter-spacing: 1.5px;margin-left:6px;">
大胆尝试 -- 常见递归问题<br/>
</section>
</h4>
</section>
</section>
<section data-autoskip="1" class="135brush _135editor" style="font-size:14px;letter-spacing: 1.5px;text-align:justify;line-height:1.75em;padding:1em 0em;color: #333;" data-role="list" data-color="rgb(137,">
<section class="_135editor" data-role="list" data-color="rgb(137,">
<section class="_135editor" data-role="list" data-color="rgb(137,">
<ol style="list-style-type: decimal;" class="list-paddingleft-2">
<li>
<p>
斐波那契数列
</p>
</li>
<section class="_135editor" data-role="list" data-color="rgb(137,">
<ol style="list-style-type: lower-alpha;" class="list-paddingleft-2">
<li>
<p>
题目地址：<a href="https://leetcode-cn.com/problems/fibonacci-number/">https://leetcode-cn.com/problems/fibonacci-number/</a>
</p>
</li>
<li>
<p>
代码截图
</p>
<p>
<img src="//p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/4d1ccd16e459451ba126f7cb546574a6~tplv-k3u1fbpfcp-zoom-1.image" data-ratio="1" alt="捕获.JPG" data-w="1" style="width:auto;"/><br/>
</p>
</li>
</ol>
</section>
<li>
<p>
爬楼梯
</p>
</li>
<section class="_135editor" data-role="list" data-color="rgb(137,">
<ol style="list-style-type: lower-alpha;" class="list-paddingleft-2">
<li>
<p>
题目地址：<a href="https://leetcode-cn.com/problems/climbing-stairs/">https://leetcode-cn.com/problems/climbing-stairs/</a>
</p>
</li>
<li>
<p>
<a href="https://leetcode-cn.com/problems/climbing-stairs/">代码截图</a>
</p>
<p>
<a href="https://leetcode-cn.com/problems/climbing-stairs/"><img src="//p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/d5436ccf8e6f4935b9245629cffbf553~tplv-k3u1fbpfcp-zoom-1.image" data-ratio="1" alt="捕获.JPG" data-w="1" style="width:auto;"/></a>
</p>
<p>
<a href="https://leetcode-cn.com/problems/climbing-stairs/"></a>
</p>
</li>
</ol>
</section>
</ol>
</section>
</section>
</section>
<section class="_135editor" data-tools="135编辑器" data-id="99083" data-color="rgb(137,">
<section style="background-color: #e9f7f8; border-top-left-radius: 15px; border-top-right-radius: 15px; color: #ffffff; margin: 10px auto; background-image: linear-gradient(116deg, #89f7fe, #66a6ff);">
<section style="padding:1em;background-image:url(https://bdn.135editor.com/files/images/editor_styles/8aea68d6e4cf5be337db4b8c2b2661e0.jpg);background-repeat: no-repeat;background-size:100%;background-position: bottom;">
<section data-autoskip="1" class="135brush" style="text-align: justify;letter-spacing: 1.5px;font-size:14px;line-height:1.75em;padding-bottom:1em;">
<p>
从上面的题目可以看出，一个复杂的题目实现起来却只用了很少的代码，关键在于如何分析题目，找到最小重复单元，抽象出每一个模块的处理逻辑，最终实现整体的功能。<br/>
</p>
<p>
<br/>
</p>
<p>
类似的问题很多，这里，推荐大家在leetCode官网针对性的连续，不要贪图数量，先针对递归专题练习，再刷其他的题目。链接在这里：<a href="https://leetcode-cn.com/problemset/algorithms/">https://leetcode-cn.com/problemset/algorithms/</a>
</p>
</section>
</section>
</section>
</section>
<section class="_135editor" data-tools="135编辑器" data-id="99269" data-color="rgb(137,">
<section style="margin: 10px auto;text-align: center;">
<section style="display: inline-block;">
<section class="assistant" style="display: flex;justify-content: flex-end;align-items: flex-end;">
<section class="assistant" style="width: 28%; height: 2px; background: #ff9d4f linear-gradient(116deg, #89f7fe, #66a6ff) repeat scroll 0% 0%; align-self: flex-end; margin-bottom: 5px; color: #ffffff;" data-width="28%"></section>
</section>
<section style="display: flex;justify-content: center;align-items: center;">
<section class="assistant" style="width:32px;margin-right: -25px;margin-top: -5px;flex-shrink: 0;transform: rotate(0deg);-webkit-transform: rotate(0deg);-moz-transform: rotate(0deg);-o-transform: rotate(0deg);">
<img class="assistant" style="width:100%;display:block;" src="//p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/27451380f7104c0a998181b0ab5c9bb2~tplv-k3u1fbpfcp-zoom-1.image" data-ratio="1.3448275862068966" data-w="29" data-width="100%"/>
</section>
<h3 class="135brush" data-brushtype="text" style="font-size: 16px; letter-spacing: 1.5px; padding: 6px 25px 6px 45px; background: #fff1e1 linear-gradient(116deg, #89f7fe, #66a6ff) repeat scroll 0% 0%; color: #ffffff; font-weight: bold;">
<span style="font-size: 24px;">三 写在文末</span><br/>
</h3>
</section>
<section class="assistant" style="display: flex;justify-content: flex-start;align-items: flex-start;">
<section class="assistant" style="width: 70%; height: 2px; background: #ff9d4f linear-gradient(116deg, #89f7fe, #66a6ff) repeat scroll 0% 0%; align-self: flex-end; margin-top: 5px; color: #ffffff;" data-width="70%"></section>
</section>
</section>
</section>
</section>
<section class="_135editor" data-tools="135编辑器" data-id="94202">
<section style="width: 96%;margin: 0px auto;" data-width="96%">
<section style="border: 2px solid #363838;border-radius:6px ;background: #d7fdfc;">
<section style="text-align: right;margin-top: -5px;margin-right: 10px;">
<section style="display: inline-block;width: 3em;">
<img class="assistant" style="width: 100%;display: block;" src="//p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/e429bb18cd2a4b40ad605002ded2c20c~tplv-k3u1fbpfcp-zoom-1.image" data-ratio="0.2916666666666667" data-width="100%" data-w="72"/>
</section>
</section>
<section style="padding:6px;">
<section style="border: 2px solid #363838;border-radius:6px ;background:#fefefe;">
<section class="135brush" data-brushtype="text" style="text-align: center;font-size:40px;padding:1em;letter-spacing:2px;">
<p style="margin-top: 30px; margin-bottom: 15px; padding: 0px; font-weight: bold; color: black; font-size: 20px;">
<span class="content">只写看得懂、有价值的技术文章</span>
</p>
</section>
</section>
</section>
</section>
</section>
</section>
<section data-role="paragraph" class="_135editor">
<p>
<br/>
</p>
</section>
</section>
</section>
</section>
Copy the code
After reading it, you will find something to like or follow
Why like and follow?
Because then the platform will recommend you more high-quality articles on topics, which can help you make faster progress
At present more than 100,000 people have followed the author
