forked from ustcwpz/USTC-CS-Courses-Resource
-
Notifications
You must be signed in to change notification settings - Fork 73
/
Copy path060-recursion.html
117 lines (112 loc) · 8.29 KB
/
060-recursion.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
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Language" content="zh-CN" />
<meta http-equiv="X-UA-Compatible" content="chrome=1">
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
<meta name="author" content="songjinghe" />
<meta name="Copyright" content="GNU Lesser General Public License" />
<meta name="description" content="Teach Yourself Scheme in Fixnum Days的简体中文译版" />
<meta name="keywords" content="scheme,教程" />
<title>第六章 递归</title>
<link rel="stylesheet" href="stylesheets/main.css">
<script>var _hmt=_hmt||[];(function(){var hm=document.createElement("script");hm.src="//hm.baidu.com/hm.js?379b64254bb382c4fa11fad6cb4e98de";var s=document.getElementsByTagName("script")[0];s.parentNode.insertBefore(hm,s);})();</script>
<script type="text/javascript">document.write(unescape("%3Cspan style='display:none' id='cnzz_stat_icon_1253043874'%3E%3C/span%3E%3Cscript src='http://s19.cnzz.com/z_stat.php%3Fid%3D1253043874' type='text/javascript'%3E%3C/script%3E"));</script>
</head>
<body>
<h1>第六章，递归</h1>
<p>一个过程体中可以包含对其它过程的调用，特别的是也可以调用自己。</p>
<pre><code class="lang-scheme">(define factorial
(lambda (n)
(if (= n 0) 1
(* n (factorial (- n 1))))))</code></pre>
<p>这个递归过程用来计算一个数的阶乘。如果这个数是0，则结果为1。对于任何其它的值n，这个过程会调用其自身来完成n-1阶乘的计算，然后将这个子结果乘上n并返回最终产生的结果。</p>
<p>互递归过程也是可以的。下面判断奇偶数的过程相互进行了调用。</p>
<pre><code class="lang-scheme">(define is-even?
(lambda (n)
(if (= n 0) #t
(is-odd? (- n 1)))))
(define is-odd?
(lambda (n)
(if (= n 0) #f
(is-even? (- n 1)))))</code></pre>
<p>这里提供的两个过程的定义仅作为简单的互递归示例。Scheme已经提供了简单的判断过程<code>even?</code>和<code>odd?</code>。</p>
<h2>6.1 letrec</h2>
<p>如果希望将上面的过程定义为局部的，我们会尝试使用let结构：</p>
<pre><code class="lang-scheme">(let ((local-even? (lambda (n)
(if (= n 0) #t
(local-odd? (- n 1)))))
(local-odd? (lambda (n)
(if (= n 0) #f
(local-even? (- n 1))))))
(list (local-even? 23) (local-odd? 23)))</code></pre>
<p>但这并不能成功，因为在初始化值过程中出现的<code>local-even?</code> 和 <code>local-odd?</code>指向的并不是这两个过程本身。</p>
<p>把<code>let</code>换成<code>let*</code>同样也不能奏效，因为这时虽然<code>local-odd?</code>中出现的<code>local-even?</code>指向的是前面刚创建好的局部的过程，但<code>local-even?</code> 中的<code>local-odd?</code>还是指向了别处。</p>
<p>为解决这个问题，Scheme提供了<code>letrec</code>结构。</p>
<pre><code class="lang-scheme">(letrec ((local-even? (lambda (n)
(if (= n 0) #t
(local-odd? (- n 1)))))
(local-odd? (lambda (n)
(if (= n 0) #f
(local-even? (- n 1))))))
(list (local-even? 23) (local-odd? 23)))</code></pre>
<p>用<code>letrec</code>创建的词法变量不仅可以在<code>letrec</code>执行体中可见而且在初始化中也可见。<code>letrec</code>是专门为局部的递归和互递归过程而设置的。(这里也可以使用<code>define</code>来创建两个子结构的方式来实现局部递归)</p>
<h2>6.2 命名let</h2>
<p>使用<code>letrec</code>定义递归过程可以实现循环。如果我们想显示10到1的降数列，可以这样写：</p>
<pre><code class="lang-scheme">(letrec ((countdown (lambda (i)
(if (= i 0) 'liftoff
(begin
(display i)
(newline)
(countdown (- i 1)))))))
(countdown 10))</code></pre>
<p>这会在控制台上输出10到1，并会返回结果<code>liftoff</code>。</p>
<p>Scheme允许使用一种叫“命名let”的<code>let</code>变体来更简洁的写出这样的循环:</p>
<pre><code class="lang-scheme">(let countdown ((i 10))
(if (= i 0) 'liftoff
(begin
(display i)
(newline)
(countdown (- i 1)))))</code></pre>
<p>注意在<code>let</code>的后面立即声明了一个变量用来表示这个循环。这个程序和先前用<code>letrec</code>写的程序是等价的。你可以将“命名let”看成一个对<code>letrec</code>结构进行扩展的宏。</p>
<h2>6.3 迭代</h2>
<p>上面定义的<code>countdown</code>函数事实上是一个递归的过程。Scheme只有通过递归才能定义循环，不存在特殊的循环或迭代结构。</p>
<p>尽管如此，上述定义的循环是一个“真”循环，与其他语言实现它们的循环的方法完全相同。也就是说,Scheme十分注意确保上面使用过的递归类型不会产生过程调用/返回开销。</p>
<p>Scheme通过一种消除尾部调用（tail-call elimination）的过程完成这个功能。如果你注意观察<code>countdown</code>的步骤，你会注意到当递归调用出现在<code>countdown</code>主体内时，就变成了“尾部调用”，或者说是最后完成的事情——<code>countdown</code>的每次调用要么不调用它自身，要么当它调用自身时把这个动作留在最后。对于一个Scheme语言的实现来说（解释器），这会使递归不同于迭代。因此，尽管用递归去写循环吧，这是安全的。</p>
<p>这是又一个有用的尾递归程序的例子：</p>
<pre><code class="lang-scheme">(define list-position
(lambda (o l)
(let loop ((i 0) (l l))
(if (null? l) #f
(if (eqv? (car l) o) i
(loop (+ i 1) (cdr l)))))))</code></pre>
<p><code>list-position</code>发现了<code>o</code>对象在列表<code>l</code>中第一次出现的索引。如果在列表中没有发现对象，过程将会返回<code>#f</code>。</p>
<p>这又是一个尾部递归过程，它将自身的参数列表就地反转，也就是使现有的列表内容产生变异，而没有分配一个新的列表：</p>
<pre><code class="lang-scheme">(define reverse!
(lambda (s)
(let loop ((s s) (r '()))
(if (null? s) r
(let ((d (cdr s)))
(set-cdr! s r)
(loop d s))))))</code></pre>
<p><code>reverse!</code>是一个十分有用的过程，它在很多Scheme方言中都能使用，例如MzScheme和Guile）</p>
<p>更多地递归例子（包括迭代）参见附录C。</p>
<h2>6.4 用自定义过程映射整个列表</h2>
<p>有一种特殊类型的迭代，对列表中每个元素，它都会重复相同的动作。Scheme为这种情况提供了两种程序：<code>map</code>和<code>for-each</code>。</p>
<p><code>map</code>程序为给定列表中的每个元素提供了一种既定程序，并返回一个结果的列表。例如：</p>
<pre><code class="lang-scheme">(map add2 '(1 2 3))
=> (3 4 5)</code></pre>
<p><code>for-each</code>程序也为列表中的每个元素提供了一个程序，但返回值为空。这个程序纯粹是产生的副作用。例如：</p>
<pre><code class="lang-scheme">(for-each display
(list "one " "two " "buckle my shoe"))</code></pre>
<p>这个程序在控制台上有显示字符串（在它们出现的顺序上）的副作用。</p>
<p>这个由<code>map</code>和<code>for-each</code>用在列表上的程序并不一定是单参数程序。举例来说，假设一个n参数的程序，<code>map</code>会接受n个列表，每个列表都是由一个参数所组成的集合，而<code>map</code>会从每个列表中取相应元素提供给程序。例如：</p>
<pre><code class="lang-scheme">(map cons '(1 2 3) '(10 20 30))
=> ((1 . 10) (2 . 20) (3 . 30))
(map + '(1 2 3) '(10 20 30))
=> (11 22 33)</code></pre>
<!-- <script src="https://google-code-prettify.googlecode.com/svn/loader/run_prettify.js"></script> -->
</body>
</html>