-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathrecursive.html
276 lines (276 loc) · 93.6 KB
/
recursive.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><meta http-equiv="X-UA-COMPATIBLE" content="IE=edge,chrome=1"><meta name="renderer" content="webkit"><link rel="icon" type="image/ico" sizes="32x32" href="/assets/favicon.ico"><link rel="apple-touch-icon" sizes="180x180" href="/assets/apple-touch-icon.png"><link rel="alternate" href="/rss.xml" title="Jiankychen's Blog" type="application/rss+xml"><link rel="alternate" href="/atom.xml" title="Jiankychen's Blog" type="application/atom+xml"><link rel="alternate" type="application/json" title="Jiankychen's Blog" href="https://jiankychen.github.io/feed.json"><link rel="preconnect" href="https://lf9-cdn-tos.bytecdntp.com"><link rel="preconnect" href="https://at.alicdn.com"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Mulish:400,400italic,700,700italic%7CFredericka%20the%20Great:400,400italic,700,700italic%7CNoto%20Serif%20JP:400,400italic,700,700italic%7CNoto%20Serif%20SC:400,400italic,700,700italic%7CInconsolata:400,400italic,700,700italic&display=swap&subset=latin,latin-ext" media="none" onload="this.media='all'"><link rel="stylesheet" href="/css/app.css?v=0.4.2"><link rel="modulepreload" href="/js/chunk-7IVLRIQ3.js"><link rel="modulepreload" href="/js/chunk-IXT6LZJL.js"><link rel="modulepreload" href="/js/chunk-PHSEV26P.js"><link rel="modulepreload" href="/js/chunk-XHQGHZCW.js"><link rel="modulepreload" href="/js/comments-TUWNDU5I.js"><link rel="modulepreload" href="/js/post-P6IN2S3Y.js"><link rel="modulepreload" href="/js/quicklink-HAJEHOPK.js"><link rel="modulepreload" href="/js/search-WFXK2K66.js"><link rel="modulepreload" href="/js/siteInit.js"><link rel="stylesheet" href="https://npm.webcache.cn/@waline/[email protected]/dist/waline.css" media="none" onload="this.media='all'"><link rel="preload" href="https://i.imgtg.com/2023/03/09/YSj7p.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/9b626c5ba21d7cb4dbcba2b507688bbb.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/65d0bfef68566882ce0560cab2e87921.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/YQSYM.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/a1f3404a5032323ea4857ac5a6354d2f.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/Y0kTl.jpg" as="image" fetchpriority="high"><meta name="keywords" content="递归"><link rel="canonical" href="https://jiankychen.github.io/recursive"><title>递推与递归</title><meta name="generator" content="Hexo 7.0.0"></head><body itemscope="" itemtype="http://schema.org/WebPage"><div id="loading"><div class="cat"><div class="body"></div><div class="head"><div class="face"></div></div><div class="foot"><div class="tummy-end"></div><div class="bottom"></div><div class="legs left"></div><div class="legs right"></div></div><div class="paw"><div class="hands left"></div><div class="hands right"></div></div></div></div><div id="container"><header id="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="inner"><div id="brand"><div class="pjax"><h1 itemprop="name headline">递推与递归</h1><div class="meta"><span class="item" title="创建时间：2022-04-21 17:11:20"><span class="icon"><i class="ic i-calendar"></i></span><span class="text">发表于</span><time itemprop="dateCreated datePublished" datetime="2022-04-21T17:11:20+08:00">2022-04-21</time></span><span class="item" title="本文字数"><span class="icon"><i class="ic i-pen"></i></span><span class="text">本文字数</span><span>8.8k</span><span class="text">字</span></span><span class="item" title="阅读时长"><span class="icon"><i class="ic i-clock"></i></span><span class="text">阅读时长</span><span>8 分钟</span></span></div></div></div><nav id="nav"><div class="inner"><div class="toggle"><div class="lines" aria-label="切换导航栏"><span class="line"></span><span class="line"></span><span class="line"></span></div></div><ul class="menu"><li class="item title"><a href="/" rel="start">Jiankychen</a></li></ul><ul class="right" id="rightNav"><li class="item theme"><i class="ic i-sun"></i></li><li class="item search"><i class="ic i-search"></i></li></ul></div></nav></div><div class="pjax" id="imgs"><ul><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/YSj7p.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/9b626c5ba21d7cb4dbcba2b507688bbb.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/65d0bfef68566882ce0560cab2e87921.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/YQSYM.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/a1f3404a5032323ea4857ac5a6354d2f.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/Y0kTl.jpg");"></li></ul></div></header><div id="waves"><svg class="waves" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 24 150 28" preserveAspectRatio="none" shape-rendering="auto"><defs><path id="gentle-wave" d="M-160 44c30 0 58-18 88-18s 58 18 88 18 58-18 88-18 58 18 88 18 v44h-352z"></path></defs><g class="parallax"><use xlink:href="#gentle-wave" x="48" y="0"></use><use xlink:href="#gentle-wave" x="48" y="3"></use><use xlink:href="#gentle-wave" x="48" y="5"></use><use xlink:href="#gentle-wave" x="48" y="7"></use></g></svg></div><main><div class="inner"><div class="pjax" id="main"><div class="article wrap"><div class="breadcrumb" itemlistelement="" itemscope="" itemtype="https://schema.org/BreadcrumbList"><i class="ic i-home"></i><span><a href="/">首页</a></span><i class="ic i-angle-right"></i><span class="current" itemprop="itemListElement" itemscope="itemscope" itemtype="https://schema.org/ListItem"><a href="/categories/Data-Structure/" itemprop="item" rel="index" title="分类于Data Structure"><span itemprop="name">Data Structure<meta itemprop="position" content="0"></span></a></span></div><article class="post block" itemscope="itemscope" itemtype="http://schema.org/Article" lang="zh-CN"><link itemprop="mainEntityOfPage" href="https://jiankychen.github.io/recursive.html"><span hidden="hidden" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><meta itemprop="image" content="/assets/avatar.jpg"><meta itemprop="name" content="Jiankychen"><meta itemprop="description" content="Never put off till tomorrow what you can do today, "></span><span hidden="hidden" itemprop="publisher" itemscope="itemscope" itemtype="http://schema.org/Organization"><meta itemprop="name" content="Jiankychen's Blog"></span><div class="body md" itemprop="articleBody"><h2 id="递推"><a class="anchor" href="#递推">#</a> 递推</h2>
<p>递推的基本思想：根据已有信息推出未知信息</p>
<p>递推解题思路：</p>
<ol>
<li>数学建模</li>
<li>找出递推式与初始条件</li>
</ol>
<h3 id="青蛙跳台阶"><a class="anchor" href="#青蛙跳台阶">#</a> 青蛙跳台阶</h3>
<p><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/">剑指 Offer 10- II. 青蛙跳台阶问题</a></p>
<p>一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 <code>n</code> 级的台阶总共有多少种跳法。结果须对 <code>1000000007</code> 取模</p>
<p>递推解题思路：</p>
<ol>
<li>
<p>假设 <code>f[n]</code> 表示 青蛙从第一个石头跳到第 <code>n</code> 个石头一共有 <code>f[n]</code> 种方案</p>
</li>
<li>
<p>递推式： <code>f[n] = f[n - 1] + f[n - 2]</code></p>
<ul>
<li>从 <code>n - 1</code> 台阶，一次跳 1 级到 <code>n</code></li>
<li>从 <code>n - 2</code> 台阶，一次跳 2 级到 <code>n</code></li>
</ul>
</li>
<li>
<p>初始条件： <code>f[0] = 1</code> , <code>f[1] = 1</code> , <code>f[2] = 2</code></p>
</li>
</ol>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 青蛙跳台阶问题</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">int</span> <span class="token function">numWays</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><=</span> <span class="token number">1</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">const</span> <span class="token keyword">int</span> MOD <span class="token operator">=</span> <span class="token number">1000000007</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">f</span><span class="token punctuation">(</span>n <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator"><=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="9"></td><td><pre> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>f<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> f<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span> <span class="token comment">// 取模 1e9+7</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token keyword">return</span> f<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<p>另，本题本质上等价于 <strong>斐波那契数列</strong> 问题，唯一差异在于起始数字不同</p>
<ul>
<li>青蛙跳台阶问题： <code>f(0) = 1</code> , <code>f(1) = 1</code> , <code>f(2) = 2</code></li>
<li>斐波那契数列问题： <code>f(0) = 0</code> , <code>f(1) = 1</code> , <code>f(2) = 1</code></li>
</ul>
<h3 id="卡特兰数"><a class="anchor" href="#卡特兰数">#</a> 卡特兰数</h3>
<p>由 <code>n</code> 对括号组成的括号序列，有多少种是合法的括号序列？其中，合法的括号序列是指：任何一个左括号都必须有与之对应的右括号，任何一个右括号都必须有与之对应的左括号。答案对 <code>998244353</code> 取模</p>
<p>递推解题思路：</p>
<ol>
<li>
<p><code>f[n]</code> 表示 <code>n</code> 对括号能够组成 <code>f[n]</code> 种合法的括号序列</p>
</li>
<li>
<p>递推式：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><msubsup><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msubsup><mrow><mi>f</mi><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo><mo>×</mo><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo>−</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow><annotation encoding="application/x-tex">f(n) = \sum\limits_{k = 0}^{n - 1} {f(k) \times f(n - k - 1)}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:2.5032em;vertical-align:-1.0021em;"></span><span class="mop op-limits"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.5011em;"><span style="top:-2.0979em;margin-left:0em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span><span class="mrel mtight">=</span><span class="mord mtight">0</span></span></span></span><span style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span><span class="mop op-symbol small-op">∑</span></span></span><span style="top:-3.95em;margin-left:0em;"><span class="pstrut" style="height:3em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">n</span><span class="mbin mtight">−</span><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:1.0021em;"><span></span></span></span></span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">×</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mord">1</span><span class="mclose">)</span></span></span></span></span></p>
<ul>
<li>括号序列可以表示为 <code>A(B)</code> ，其中， <code>A</code> 和 <code>B</code> 都是合法括号序列（ <code>A</code> 和 <code>B</code> 可以是空序列）</li>
<li><code>f(k)</code> 表示包含 <code>k</code> 对括号的合法序列 <code>A</code> 的种类数</li>
<li><code>f(n - k - 1)</code> 表示包含 <code>n - k - 1</code> 对括号的合法序列 <code>B</code> 的种类数</li>
</ul>
</li>
<li>
<p>初始条件： <code>f[0] = 1</code></p>
<ul>
<li><code>0</code> 对括号能组成一种括号序列（空序列）</li>
</ul>
</li>
</ol>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 计算卡特兰数</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">int</span> <span class="token function">CatalanNumber</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><=</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">const</span> <span class="token keyword">int</span> MOD <span class="token operator">=</span> <span class="token number">998244353</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">f</span><span class="token punctuation">(</span>n <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> f<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// 初始条件</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator"><=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 求 f [i] 的值</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> k <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> k <span class="token operator"><</span> i<span class="token punctuation">;</span> k<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="10"></td><td><pre> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">+=</span> <span class="token keyword">int</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span><span class="token punctuation">)</span> f<span class="token punctuation">[</span>k<span class="token punctuation">]</span> <span class="token operator">*</span> f<span class="token punctuation">[</span>i <span class="token operator">-</span> k <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">%</span> MOD<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 递推式</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token comment">// 注意，两个 int 相乘的结果可能爆 int ，因此乘法的过程要转换成 long long 以避免整数溢出</span></pre></td></tr><tr><td data-num="12"></td><td><pre> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">%=</span> MOD<span class="token punctuation">;</span> <span class="token comment">// 取模</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token keyword">return</span> f<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.0641em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span></p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<h3 id="错位排列"><a class="anchor" href="#错位排列">#</a> 错位排列</h3>
<p>有 <code>n</code> 个信封和 <code>n</code> 个信件，第 <code>i</code> 个信件属于第 <code>i</code> 个信封，我们想知道，有多少种不同的方法，使得没有任何一个信件被装入正确的信封中？答案对 <code>998244353</code> 取模</p>
<p>解题思路：</p>
<ol>
<li>
<p>令 <code>f[i]</code> 表示信件和信封数量为 <code>i</code> 时的总方案数</p>
</li>
<li>
<p>递推式： <code>f[n] = (n - 1) * (f[n - 1] + f[n - 2])</code></p>
<ul>
<li>考虑 1 号信件，它不能被装入 1 号信封，不妨假设它被装入了 x 号信封，那么 x 号信件可以装入哪个信封呢？</li>
<li>第一种情况：x 号信件装入了 1 号信封。此时可以去掉 1 号和 x 号，原问题简化成： <code>n - 2</code> 个信件和信封的错位排列问题，一共有 <code>f[n - 2]</code> 种方案</li>
<li>第二种情况：x 号信件没有装入 1 号信封。即，x 号信件应与 1 号信封错位，此时原问题等价于一个大小为 <code>n - 1</code> 的错位排列问题，一共有 <code>f[n - 1]</code> 种方案</li>
<li>并且，x 的选择有 <code>n - 1</code> 种（除了 1 号都可以）</li>
</ul>
</li>
<li>
<p>初始条件： <code>f[1] = 0</code> , <code>f[2] = 1</code></p>
<ul>
<li>只有 1 个信件和信封时，无法错位排列</li>
<li>有 2 个信件和信封时，只有一种排列方案</li>
</ul>
</li>
</ol>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span> <span class="token function">SolutionNumber</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">f</span><span class="token punctuation">(</span>n <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">const</span> <span class="token keyword">int</span> MOD <span class="token operator">=</span> <span class="token number">998244353</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> f<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// 初始条件</span></pre></td></tr><tr><td data-num="7"></td><td><pre> f<span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">3</span><span class="token punctuation">;</span> i <span class="token operator"><=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="9"></td><td><pre> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token keyword">long</span><span class="token punctuation">)</span> <span class="token punctuation">(</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token punctuation">(</span>f<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> f<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="11"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<h3 id="杨辉三角二维递推"><a class="anchor" href="#杨辉三角二维递推">#</a> 杨辉三角（二维递推）</h3>
<p>给定 <code>k</code> ，你需要输出一个 <code>(k + 1) * (k + 1)</code> 的矩阵，其中，第 <code>i</code> 行第 <code>j</code> 列元素表示：从 <code>i</code> 个不同的物品中选出 <code>j</code> 个的方案数（行和列的标号从 0 开始）。所有答案对 <code>998244353</code> 取模</p>
<p>比如，当 k = 4 时，输出如下矩阵：</p>
<pre><code>1 0 0 0 0
1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1
</code></pre>
<p>解题思路：</p>
<ol>
<li>
<p>二维数组的元素 <code>f[i][j]</code> 表示从 <code>i</code> 个物品中选 <code>j</code> 个的方案数</p>
</li>
<li>
<p>递推式： <code>f[i][j] = f[i - 1][j - 1] + f[i - 1][j]</code></p>
<ul>
<li>考虑 1 号物品：选，或者不选</li>
<li>选 1 号物品：那么接下来还需要从剩下的 <code>i - 1</code> 个物品中选出 <code>j - 1</code> 个，方案数为 <code>f[i - 1][j - 1]</code></li>
<li>不选 1 号物品：那么需要从 <code>i - 1</code> 个物品中选出 <code>j</code> 个，方案数为 <code>f[i - 1][j]</code></li>
</ul>
</li>
<li>
<p>边界条件： <code>f[i][0] = f[i][i] = 1</code></p>
<ul>
<li>所有 <code>j = 0</code> 的位置和 <code>j = i</code> 的位置都是 <code>1</code> ， 分别对应 所有物品都不选 和 所有物品都选取</li>
<li>所有 <code>j > i</code> 的位置都是 <code>0</code> ，因为选出物品不可能多于 <code>i</code></li>
</ul>
</li>
</ol>
<p>注意，二维递推不同于一维递推，二维的数据可能存在莫名其妙的依赖关系，因此我们在写二维递推的时候，需要特别注意二维 <strong>递推的顺序</strong></p>
<p>在此例中， <code>f[i]</code> 这一行的值全部由 <code>f[i - 1]</code> 这一行的值推出，因此，只需要按照行数从小到大的顺序递推即可</p>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">void</span> <span class="token function">Triangle</span><span class="token punctuation">(</span><span class="token keyword">int</span> k<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>k <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">const</span> <span class="token keyword">int</span> MOD <span class="token operator">=</span> <span class="token number">998244353</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">int</span> f<span class="token punctuation">[</span>k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>k <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">}</span><span class="token punctuation">;</span> <span class="token comment">// 初始化二维数组</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><=</span> k<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="7"></td><td><pre> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// 边界条件</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator"><</span> i<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="9"></td><td><pre> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span>f<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> f<span class="token punctuation">[</span>i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">%</span> MOD<span class="token punctuation">;</span> <span class="token comment">// 递推式，需要取模</span></pre></td></tr><tr><td data-num="10"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator"><=</span> k<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="12"></td><td><pre> cout <span class="token operator"><<</span> f<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator"><<</span> <span class="token char">' '</span><span class="token punctuation">;</span> <span class="token comment">// 输出这一整行</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="14"></td><td><pre> cout <span class="token operator"><<</span> endl<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="16"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.0641em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span></p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mi>n</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n^2)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.0641em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span></p>
<p><a target="_blank" rel="noopener" href="https://www.boyuai.com/learn/courses/149/lessons/2537/steps/0?from=qz">青舟智学：递推与递推思想的应用</a></p>
<h2 id="递归"><a class="anchor" href="#递归">#</a> 递归</h2>
<p>递归（Recursion）的基本思想：某个函数直接或者间接地调用自身</p>
<p>递归有两个显著的特征:</p>
<ul>
<li>自身调用：原问题可以分解为 <strong>具有相同解决思路</strong> 的 <strong>子问题</strong> ，即都是调用自身的同一个函数</li>
<li>终止条件：递归必须有一个 <strong>终止条件</strong> ，而不能无限循环地调用本身</li>
</ul>
<p>因此，首先需要根据以上两个特点来判断题目是否可以用递归算法</p>
<p>递归的经典应用场景：</p>
<ul>
<li>阶乘问题</li>
<li>二叉树深度</li>
<li>汉诺塔问题</li>
<li>斐波那契数列</li>
<li>快速排序、归并排序（分治算法体现递归）</li>
<li>遍历文件，解析 xml 文件</li>
</ul>
<p>递归解题思路：</p>
<ol>
<li>定义函数，明确函数的功能：确认并牢记这个递归函数的功能，不要让一个函数干两件事情！</li>
<li>寻找原问题与子问题的关系：即，确定递推公式</li>
<li>确定递归终止条件：发现递推关系后，要寻找 <strong>不可再分解的子问题的解</strong> ，即，临界条件，确保子问题不会无限分解下去</li>
<li>推导时间复杂度，如果发现递归时间复杂度不可接受，则需 <strong>转换思路对其进行改造</strong></li>
</ol>
<blockquote>
<p>只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的</p>
<p>千万不要尝试研究这个递归的过程是什么样的！</p>
</blockquote>
<p>递归算法的时间复杂度：<strong> <code>递归时间复杂度 = 解决一个子问题的时间 * 子问题的个数</code> </strong></p>
<ul>
<li>可以将递归过程抽象成一棵 “递归树”，树中每一个节点都是一次递归，所以该递归算法的时间复杂度为 <code>节点数 * 每个节点的时间复杂度</code></li>
</ul>
<p>递归算法的空间复杂度：<strong> <code>递归算法的空间复杂度 = 每次递归的空间复杂度 * 递归深度</code> </strong></p>
<ul>
<li>每次递归所需的空间都被压到调用栈里，调用栈的最大长度就是递归的深度</li>
</ul>
<p><a target="_blank" rel="noopener" href="https://www.programmercarl.com/%E5%89%8D%E5%BA%8F/%E9%80%9A%E8%BF%87%E4%B8%80%E9%81%93%E9%9D%A2%E8%AF%95%E9%A2%98%E7%9B%AE%EF%BC%8C%E8%AE%B2%E4%B8%80%E8%AE%B2%E9%80%92%E5%BD%92%E7%AE%97%E6%B3%95%E7%9A%84%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%EF%BC%81.html">代码随想录：通过一道面试题目，讲一讲递归算法的时间复杂度！</a></p>
<p>递归存在的问题：</p>
<ol>
<li><strong>栈溢出</strong>
<ul>
<li>递归是利用堆栈来实现的。每当进入一个函数调用，栈就会增加一层栈帧，每次函数返回，栈就会减少一层栈帧。若递归调用层级太多，就会超出栈的容量</li>
<li>解决方案：减少递归调用次数；改用其他算法</li>
</ul>
</li>
<li><strong>重复计算</strong>
<ul>
<li>递归过程中可能会重复求解某些子问题，导致效率低下</li>
<li>解决方案：记录已经遍历过的状态（记忆化递归）；改用其他算法（例如，迭代算法）</li>
</ul>
</li>
</ol>
<p><a target="_blank" rel="noopener" href="https://www.programmercarl.com/%E5%89%8D%E5%BA%8F/%E9%80%92%E5%BD%92%E7%AE%97%E6%B3%95%E7%9A%84%E6%97%B6%E9%97%B4%E4%B8%8E%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%88%86%E6%9E%90.html#%E9%80%92%E5%BD%92%E6%B1%82%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97%E7%9A%84%E6%80%A7%E8%83%BD%E5%88%86%E6%9E%90">代码随想录：递归求斐波那契数列的性能分析</a></p>
<h3 id="阶乘"><a class="anchor" href="#阶乘">#</a> 阶乘</h3>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 递推写法</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">int</span> <span class="token function">factorial</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">//n 不小于 0</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><=</span> <span class="token number">1</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">int</span> ans <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">2</span><span class="token punctuation">;</span> i <span class="token operator"><=</span> n<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="7"></td><td><pre> ans <span class="token operator">=</span> i <span class="token operator">*</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">return</span> ans<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="10"></td><td><pre></pre></td></tr><tr><td data-num="11"></td><td><pre><span class="token comment">// 递归写法</span></pre></td></tr><tr><td data-num="12"></td><td><pre><span class="token keyword">int</span> <span class="token function">recursion</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 计算 n 的阶乘</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><</span> <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token comment">// 递归终止条件</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre> <span class="token keyword">return</span> n <span class="token operator">*</span> <span class="token function">recursion</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 递推公式</span></pre></td></tr><tr><td data-num="16"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>递推算法</p>
<ul>
<li>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></li>
<li>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></li>
</ul>
<p>递归算法</p>
<ul>
<li>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，递归 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 次</li>
<li>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，调用栈深度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span></li>
</ul>
<h3 id="青蛙跳台阶-2"><a class="anchor" href="#青蛙跳台阶-2">#</a> 青蛙跳台阶</h3>
<p>递归的简单实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 非记忆化递归</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">int</span> <span class="token function">f</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// 计算青蛙跳到 n 级台阶的方案数</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><=</span> <span class="token number">1</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">return</span> <span class="token function">f</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">f</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mn>2</mn><mi>n</mi></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(2^n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.6644em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span></p>
<ul>
<li>将递归过程抽象成一颗深度为 <code>n</code> 的 “递归树”（每一个节点都是一次递归），最多有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mi>n</mi></msup><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2^n - 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7477em;vertical-align:-0.0833em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.6644em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> 个节点，每次递归的时间复杂度均为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span>，所以该递归算法的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mn>2</mn><mi>n</mi></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(2^n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.6644em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span></li>
</ul>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<ul>
<li>每次递归的空间复杂度是 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span>，递归的深度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span></li>
</ul>
<p>分析发现，在递归过程中， <code>f(n - 1) + f(n - 2)</code> 存在大量的重复计算，因此，可以考虑将已经计算过的结果保存起来，即，带备忘录的递归解法，实现 <strong>以空间换时间</strong></p>
<p>一般使用一个数组充当这个「备忘录」，当然也可以使用「哈希表」</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 数组充当备忘录</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">int</span> <span class="token function">fib</span><span class="token punctuation">(</span><span class="token keyword">int</span> N<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>N <span class="token operator"><</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> <span class="token function">memo</span><span class="token punctuation">(</span>N <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 备忘录全初始化为 0</span></pre></td></tr><tr><td data-num="6"></td><td><pre> </pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">return</span> <span class="token function">helper</span><span class="token punctuation">(</span>memo<span class="token punctuation">,</span> N<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="9"></td><td><pre></pre></td></tr><tr><td data-num="10"></td><td><pre><span class="token keyword">int</span> <span class="token function">helper</span><span class="token punctuation">(</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span><span class="token operator">&</span> memo<span class="token punctuation">,</span> <span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="11"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator">==</span> <span class="token number">0</span> <span class="token operator">||</span> n <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// base case </span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>memo<span class="token punctuation">[</span>n<span class="token punctuation">]</span> <span class="token operator">!=</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token keyword">return</span> memo<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">;</span> <span class="token comment">// 已经计算过</span></pre></td></tr><tr><td data-num="15"></td><td><pre> memo<span class="token punctuation">[</span>n<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token function">helper</span><span class="token punctuation">(</span>memo<span class="token punctuation">,</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">helper</span><span class="token punctuation">(</span>memo<span class="token punctuation">,</span> n <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="16"></td><td><pre> <span class="token keyword">return</span> memo<span class="token punctuation">[</span>n<span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="17"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="18"></td><td><pre></pre></td></tr><tr><td data-num="19"></td><td><pre></pre></td></tr><tr><td data-num="20"></td><td><pre><span class="token comment">// 哈希表充当备忘录</span></pre></td></tr><tr><td data-num="21"></td><td><pre><span class="token keyword">int</span> <span class="token function">f</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="22"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="23"></td><td><pre> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="24"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><=</span> <span class="token number">1</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="25"></td><td><pre> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="26"></td><td><pre> <span class="token comment">//map 即保存中间态的键值对， key 为 n，value 即 f (n)</span></pre></td></tr><tr><td data-num="27"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>map<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="28"></td><td><pre> <span class="token keyword">return</span> map<span class="token punctuation">.</span><span class="token function">get</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="29"></td><td><pre> <span class="token punctuation">}</span></pre></td></tr><tr><td data-num="30"></td><td><pre> <span class="token keyword">return</span> <span class="token function">f</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">f</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="31"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>带备忘录的递归解法的时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，“递归树” 一共 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 个节点</p>
<p>带备忘录的递归解法的空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，递归深度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span>，且用了一个键值对来保存中间的计算结果</p>
<p>另一种优化方案：用 <code>first</code> 和 <code>second</code> 来记录递推公式中相加的两个数值，此时就不用两次递归，从而减少了递归的调用次数</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span> <span class="token function">f</span><span class="token punctuation">(</span><span class="token keyword">int</span> first<span class="token punctuation">,</span> <span class="token keyword">int</span> second<span class="token punctuation">,</span> <span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">return</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><=</span> <span class="token number">1</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token keyword">return</span> <span class="token number">1</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token keyword">else</span> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token keyword">return</span> first <span class="token operator">+</span> second<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre> <span class="token keyword">else</span></pre></td></tr><tr><td data-num="9"></td><td><pre> <span class="token keyword">return</span> <span class="token function">f</span><span class="token punctuation">(</span>second<span class="token punctuation">,</span> first <span class="token operator">+</span> second<span class="token punctuation">,</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，递归 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 次</p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span>，递归深度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span></p>
<h3 id="汉诺塔"><a class="anchor" href="#汉诺塔">#</a> 汉诺塔</h3>
<p>如下图所示的汉诺塔问题，从左到右有 A、B、C 三根柱子，其中 A 柱子上面有从小叠到大的 <code>n</code> 个圆盘，现要求将 A 柱子上的圆盘移到 C 柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤</p>
<p><img loading="lazy" data-src="AL-%E9%80%92%E6%8E%A8%E4%B8%8E%E9%80%92%E5%BD%92/hanoid.webp" alt=""></p>
<p>递归求解思路：</p>
<ol>
<li>
<p>定义问题的递归函数：函数的功能为 把 A 上面的 <code>n</code> 个圆盘经由 B 移到 C</p>
</li>
<li>
<p>查找问题与子问题的关系</p>
<ul>
<li>
<p>将 A 最上面的 <code>n - 1</code> 个圆盘视为一个整体</p>
</li>
<li>
<p>递归函数的实现步骤为：1） 将 A 上面的 <code>n - 1</code> 个圆盘经由 C 移到 B ；2）将 A 最底下的圆盘移到 C ；3）将 B 上的 <code>n - 1</code> 个圆盘经由 A 移到 C 上</p>
</li>
</ul>
</li>
<li>
<p>递归终止条件：A 上不再有圆盘（所有圆盘已经移到 C 上）</p>
</li>
</ol>
<blockquote>
<p>这里不需要深究 “具体怎么把 <code>n - 1</code> 个圆盘从 A 移到 B ”，只需明白其可以通过递归实现即可</p>
<p>在确定原问题与子问题的关系时，切忌把子问题层层展开，只要找到一层问题与子问题的关系得出可以用递归表示即可</p>
</blockquote>
<p>代码实现：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 将 n 个圆盘从 a 经由 b 移动到 c 上</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">void</span> <span class="token function">move</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">,</span> <span class="token keyword">char</span> a<span class="token punctuation">,</span> <span class="token keyword">char</span> b<span class="token punctuation">,</span> <span class="token keyword">char</span> c<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><=</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="4"></td><td><pre> <span class="token keyword">return</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token function">move</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> a<span class="token punctuation">,</span> c<span class="token punctuation">,</span> b<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 将 a 上面的 n - 1 个圆盘经由 c 移到 b</span></pre></td></tr><tr><td data-num="6"></td><td><pre> cout <span class="token operator"><<</span> a <span class="token operator"><<</span> <span class="token string">" -> "</span> <span class="token operator"><<</span> b <span class="token operator"><<</span> endl<span class="token punctuation">;</span> <span class="token comment">// 将 a 底下的那块最大的圆盘移到 c</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token function">move</span><span class="token punctuation">(</span>n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">,</span> b<span class="token punctuation">,</span> a<span class="token punctuation">,</span> c<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 再将 b 上的 n-1 个圆盘经由 a 移到 c 上</span></pre></td></tr><tr><td data-num="8"></td><td><pre><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="9"></td><td><pre></pre></td></tr><tr><td data-num="10"></td><td><pre><span class="token comment">// 求解汉诺塔问题</span></pre></td></tr><tr><td data-num="11"></td><td><pre><span class="token keyword">void</span> <span class="token function">Hanoi</span><span class="token punctuation">(</span><span class="token keyword">int</span> n<span class="token punctuation">)</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="12"></td><td><pre> <span class="token keyword">if</span> <span class="token punctuation">(</span>n <span class="token operator"><=</span> <span class="token number">0</span><span class="token punctuation">)</span></pre></td></tr><tr><td data-num="13"></td><td><pre> <span class="token keyword">return</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="14"></td><td><pre> <span class="token function">move</span><span class="token punctuation">(</span>n<span class="token punctuation">,</span> <span class="token char">'A'</span><span class="token punctuation">,</span> <span class="token char">'B'</span><span class="token punctuation">,</span> <span class="token char">'C'</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="15"></td><td><pre><span class="token punctuation">}</span></pre></td></tr></tbody></table></figure><blockquote>
<p>明确函数的功能非常重要，按着函数的功能来理清 / 解释算法思路</p>
</blockquote>
<p>时间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><msup><mn>2</mn><mi>n</mi></msup><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(2^n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.6644em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">n</span></span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span></p>
<p>空间复杂度：<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<p>参考资料：</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://mp.weixin.qq.com/s/JLbjzCdVlJ_de2uGgBsUzw">CodeSheep：一文彻底学会递归思路解题</a></li>
<li><a target="_blank" rel="noopener" href="https://mp.weixin.qq.com/s/tqGKHZzSyDBgEp-oWsOztQ">CodeSheep：死磕程序员必备算法：递归！</a></li>
</ul>
<div class="tags"><a href="/tags/%E9%80%92%E5%BD%92/" rel="tag"><i class="ic i-tag"></i>递归</a></div></div><footer><div class="meta"><span class="item"><span class="icon"><i class="ic i-calendar-check"></i></span><span class="text">更新于</span><time title="修改时间：2024-06-08 23:07:47" itemprop="dateModified" datetime="2024-06-08T23:07:47+08:00">2024-06-08</time></span></div><div id="copyright"><ul><li class="author"><strong>本文作者：</strong>Jiankychen<i class="ic i-at"><em>@</em></i>Jiankychen's Blog</li><li class="link"><strong>本文链接：</strong><a href="https://jiankychen.github.io/recursive.html" title="递推与递归">https://jiankychen.github.io/recursive.html</a></li><li class="license"><strong>版权声明：</strong>本站所有文章除特别声明外，均采用 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh"><i class="ic i-creative-commons"><em>(CC)</em></i>BY-NC-SA</a> 许可协议。转载请注明出处！</li></ul></div></footer></article></div><div class="post-nav"><div class="item left"><a href="/sort-algorithm.html" rel="prev" itemprop="url" data-background-image="https://i.imgtg.com/2023/03/09/Y0zdB.jpg" title="排序"><span class="type">上一篇</span><span class="category"><i class="ic i-flag"></i>Data Structure</span><h3>排序</h3></a></div><div class="item right"><a href="/dynamic-programming.html" rel="next" itemprop="url" data-background-image="https://i.imgtg.com/2023/03/09/Y0xvg.jpg" title="动态规划"><span class="type">下一篇</span><span class="category"><i class="ic i-flag"></i>Data Structure</span><h3>动态规划</h3></a></div></div><div class="wrap" id="comments"></div></div><div id="sidebar"><div class="inner"><div class="panels"><div class="inner"><div class="contents panel pjax" data-title="文章目录"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%80%92%E6%8E%A8"><span class="toc-number">1.</span> <span class="toc-text"> 递推</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%9D%92%E8%9B%99%E8%B7%B3%E5%8F%B0%E9%98%B6"><span class="toc-number">1.1.</span> <span class="toc-text"> 青蛙跳台阶</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0"><span class="toc-number">1.2.</span> <span class="toc-text"> 卡特兰数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%94%99%E4%BD%8D%E6%8E%92%E5%88%97"><span class="toc-number">1.3.</span> <span class="toc-text"> 错位排列</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92%E4%BA%8C%E7%BB%B4%E9%80%92%E6%8E%A8"><span class="toc-number">1.4.</span> <span class="toc-text"> 杨辉三角（二维递推）</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%80%92%E5%BD%92"><span class="toc-number">2.</span> <span class="toc-text"> 递归</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%98%B6%E4%B9%98"><span class="toc-number">2.1.</span> <span class="toc-text"> 阶乘</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%9D%92%E8%9B%99%E8%B7%B3%E5%8F%B0%E9%98%B6-2"><span class="toc-number">2.2.</span> <span class="toc-text"> 青蛙跳台阶</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%B1%89%E8%AF%BA%E5%A1%94"><span class="toc-number">2.3.</span> <span class="toc-text"> 汉诺塔</span></a></li></ol></li></ol></div><div class="related panel pjax" data-title="系列文章"><ul><li><a href="/binary-search.html" rel="bookmark" title="二分查找">二分查找</a></li><li><a href="/binary-tree.html" rel="bookmark" title="二叉树">二叉树</a></li><li><a href="/algorithm-complexity.html" rel="bookmark" title="算法复杂度">算法复杂度</a></li><li><a href="/date-structure.html" rel="bookmark" title="数据结构简介">数据结构简介</a></li><li><a href="/sort-algorithm.html" rel="bookmark" title="排序">排序</a></li><li class="active"><a href="/recursive.html" rel="bookmark" title="递推与递归">递推与递归</a></li><li><a href="/dynamic-programming.html" rel="bookmark" title="动态规划">动态规划</a></li><li><a href="/priority-queue.html" rel="bookmark" title="优先级队列">优先级队列</a></li><li><a href="/hash-table.html" rel="bookmark" title="哈希表">哈希表</a></li><li><a href="/graphics-theory.html" rel="bookmark" title="图">图</a></li><li><a href="/KMP.html" rel="bookmark" title="KMP 算法">KMP 算法</a></li><li><a href="/traverse.html" rel="bookmark" title="回溯">回溯</a></li><li><a href="/Dijkstra.html" rel="bookmark" title="Dijkstra">Dijkstra</a></li></ul></div><div class="overview panel" data-title="站点概览"><div class="author" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><img class="image" loading="lazy" decoding="async" itemprop="image" alt="Jiankychen" src="/assets/avatar.webp"><p class="name" itemprop="name">Jiankychen</p><div class="description" itemprop="description"></div></div><nav class="state"><div class="item posts"><a href="/archives/"><span class="count">51</span><span class="name">文章</span></a></div><div class="item categories"><a href="/categories/"><span class="count">8</span><span class="name">分类</span></a></div><div class="item tags"><a href="/tags/"><span class="count">20</span><span class="name">标签</span></a></div></nav><div class="social"><a target="_blank" rel="noopener" href="https://github.com/jiankychen" class="item github" title="https://github.com/jiankychen"><i class="ic i-github"></i></a><a href="mailto:[email protected]" class="item email" title="mailto:[email protected]"><i class="ic i-envelope"></i></a><a target="_blank" rel="noopener" href="https://music.163.com/#/user/home?id=447771275" class="item music" title="https://music.163.com/#/user/home?id=447771275"><i class="ic i-cloud-music"></i></a><a target="_blank" rel="noopener" href="https://www.zhihu.com/people/jiankychen" class="item zhihu" title="https://www.zhihu.com/people/jiankychen"><i class="ic i-zhihu"></i></a></div><div class="menu"><li class="item"><a href="/" rel="section"><i class="ic i-home"></i>首页</a></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>文章</a><ul class="submenu"><li class="item"><a href="/archives/" rel="section"><i class="ic i-list-alt"></i>归档</a></li><li class="item"><a href="/categories/" rel="section"><i class="ic i-th"></i>分类</a></li><li class="item"><a href="/tags/" rel="section"><i class="ic i-tags"></i>标签</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>链接</a><ul class="submenu"><li class="item"><a href="/peers/" rel="section"><i class="ic i-magic"></i>链环</a></li><li class="item"><a href="/friends/" rel="section"><i class="ic i-heart"></i>友链</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-stars"></i>关于</a><ul class="submenu"><li class="item"><a href="/owner/" rel="section"><i class="ic i-user"></i>关于博主</a></li><li class="item"><a href="/site/" rel="section"><i class="ic i-paw"></i>关于本站</a></li><li class="item"><a href="/update/" rel="section"><i class="ic i-cloud"></i>更新日志</a></li></ul></li></div></div></div></div><ul id="quick"><li class="prev pjax"><a href="/dynamic-programming.html" rel="prev" title="上一篇"><i class="ic i-chevron-left"></i></a></li><li class="up"><i class="ic i-arrow-up"></i></li><li class="down"><i class="ic i-arrow-down"></i></li><li class="next pjax"><a href="/sort-algorithm.html" rel="next" title="下一篇"><i class="ic i-chevron-right"></i></a></li><li class="percent"></li></ul></div></div><div class="dimmer"></div></div></main><footer id="footer"><div class="inner"><div class="widgets"><div class="rpost pjax"><h2>随机文章</h2><ul><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-binarysearch.html">LeetCode - 二分查找专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-conda.html">conda 常用命令</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/C/" title="分类于C++">C++</a></div><span><a href="/cpp-statement.html">C++ 语句</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/binary-search.html">二分查找</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-analog.html">LeetCode - 模拟专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-doublepointer.html">LeetCode - 双指针专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/C/" title="分类于C++">C++</a></div><span><a href="/cpp-variables.html">C++ 变量和基本类型</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-basics.html">Python 基本语法</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-container.html">Python 数据容器</a></span></li><li class="item"><div class="breadcrumb"></div><span><a href="/job.html">23 求职笔面试</a></span></li></ul></div><div class="rpost pjax"><h2>最新评论</h2><ul class="leancloud-recent-comment" id="new-comment"></ul></div></div><div class="status"><div class="copyright">© 2021 -<span itemprop="copyrightYear">2024</span><span class="with-love"><i class="ic i-sakura rotate"></i></span><span class="author" itemprop="copyrightHolder">Jiankychen @ Jiankychen</span></div><div class="count"><span class="post-meta-item-icon"><i class="ic i-chart-area"></i></span><span title="站点总字数">955k 字</span><span class="post-meta-divider"> | </span><span class="post-meta-item-icon"><i class="ic i-coffee"></i></span><span title="站点阅读时长">14:28</span></div><div class="powered-by">基于 <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a> & Theme.<a target="_blank" rel="noopener" href="https://github.com/theme-shoka-x/hexo-theme-shokaX/">ShokaX</a></div></div><script src="https://unpkg.com/[email protected]/bsz.pure.mini.js"></script><div id="busuanzi-wrap"><span class="ic i-eye"></span><span id="busuanzi_container_site_pv">本站总访问量 <span id="busuanzi_value_site_pv"></span> 次</span> | <span class="ic i-user"></span><span id="busuanzi_container_site_uv">本站总访客量 <span id="busuanzi_value_site_uv"></span> 次</span></div></div></footer></div><script data-config="" type="text/javascript">var LOCAL = {
ispost: true,
path: `/recursive`,
favicon: {
show: `Jiankychen`,
hide: `Jiankychen`
},
search: {
placeholder: "文章搜索",
empty: "关于 「 ${query} 」，什么也没搜到",
stats: "${time} ms 内找到 ${hits} 条结果"
},
copy_tex: true,
katex: true,
mermaid: false,
audio: undefined,
fancybox: true,
nocopy: false,
outime: true,
template: `<div class="note warning"><p><span class="label warning">文章时效性提示</span><br>这是一篇发布于 {{publish}} 天前，最后一次更新在 {{updated}} 天前的文章，部分信息可能已经发生改变，请注意甄别。</p></div>`,
quiz: {
choice: `单选题`,
multiple: `多选题`,
true_false: `判断题`,
essay: `问答题`,
gap_fill: `填空题`,
mistake: `错题备注`
},
ignores: [
(uri) => uri.includes('#'),
(uri) => new RegExp(LOCAL.path + '$').test(uri),
[]
]
};
</script><script src="https://lf9-cdn-tos.bytecdntp.com/cdn/expire-6-M/pace/1.2.4/pace.min.js" async=""></script><script src="https://polyfill.io/v3/polyfill.min.js?features=default,fetch" defer=""></script><script src="/js/siteInit.js?v=0.4.2" type="module" fetchpriority="high" defer=""></script></body></html>