【Scheme】Scheme 编程学习 (四) —— 递归

在 Scheme 中函数的通常写法，the normal way to write functions in Scheme，通常会用到递归 (recursion)，本节的主要内容为

• Factorial 阶乘
• Fibonacci 斐波那契
• Countdown 倒计时
• Map
• Recursion “shapes” 不同形式的递归
• Tail call optimisation 尾调用优化
• Iterative forms
• Discussion

为了更好的理解递归如何运行 (make it easier for understand how recursion works)

1. Factorial 阶乘

(define (fact n)(if (= 0 n)1(* n (fact (- n 1)))))

定义 fact 函数，只接受一个入参 n，当 n 为 0 时结束，其他情况调用 n 乘以 fact(n-1)，此函数调用自身，即递归调用，类似的 C语言代码为：

int fact(int n)
{if (0 == n)return 1;elsereturn n * fact(n-1);
}

> (fact 3)
; 6
> (fact 4)
; 24
> (fact 5)
; 120

2. Fibonacci 斐波那契数列

(define (fib n)(if (<= n 2)1(+ (fib (- n 1))(fib (- n 2)))))

此函数也是经典的斐波那契序列，经典的递归编程题，此函数写为 C语言为：

int fib(int n)
{if (n <= 2)return 1;else return fib(n-1) + fib(n-2);
}

> (fib 3)
; 2
> (fib 4)
; 3
> (fib 5)
; 5
> (fib 6)
; 8

3. Countdown 倒计时

(define (countdown n)(if (= n 0)null(begin(display n) ; 打印 n (newline) ; 换行(countdown (- n 1)))))

这是一个比较简单的递归，没太多需要讲解的内容，打印显示，换行，递归调用 入参减一。
begin 用于将后续的三个语句合在一起，类似于 C语言中的大括号，我们都知道 if / else 分支在不写大括号时，最多后跟一个语句。为了使 else 分支可以调用此三个语句，可以写为 C语言

void countdown(int n)
{if (n == 0)return;else{printf("%d", n);printf("\n");countdown(n - 1);}
}

> (countdown 4)
4
3
2
1
() ; null / empty list

4. Map

这次我们再来看一下 map 函数，map 是一个 built-in (内置)函数，这里是一个实现尝试，对表 lst 中的每个元素应用函数 fn，

(define (my-map fn lst)(if (null? lst)null(cons (fn (car lst))(my-map fn (cdr lst)))))

类似的 C语言函数可尝试写为

int abs(int a) { a >= 0 ? return a : return -a; }
int (*f)(int) = abs;void my_map(int (*comp)(int), int arr[], int n)
{if (0 == n)return;else{arr[0] = comp(arr[0]);my_map(comp, arr+1, n-1);}
}

> (my-map abs (list 2 -3 4))
; (2 3 4) 

int arr[] = {2, -3, 4};
int n = sizeof(arr);
my_map(f, arr, n);

5. Recursion “shapes” 递归的形式

5.1 factorial model

(define (fact n)(if (= 0 n)1(* n (fact (- n 1))))

让我们尝试一下 (fact 3) 看看内部发生了什么

(fact 3) ; 当我们调用 (fact 3) 时 内部为:
(* 3 (fact 2)); 接下来我们展开 (fact 2)
(* 3 (* 2 (fact 1))) ; 接着展开 (fact 1)
(* 3 (* 2 (* 1 (fact 0))));展开 (fact 0) 为 1
(* 3 (* 2 (* 1 1))); 先计算 (* 1 1) 结果为 1
(* 3 (* 2 1)); 再计算 (* 2 1) 结果为 2
(* 3 2); 计算 (* 3 2) 结果为 6
6

5.2 - fibonacci model

(define (fib n)(if (<= n 2)1(+ (fib (- n 1))(fib (- n 2)))))

调用斐波那契函数并设置 n 为 5

(fib 5)
(+ (fib 4) (fib 3)); 展开为 (fib 4) 和 (fib 3) 的和，再展开 (fib 4) 和 (fib 3)
(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1))); 为 (fib 3) (fib 2) 的和 与 (fib 2) (fib 1) 的和之和 
(+ (+ (+ (fib 2) (fib 1)) 1) (+ 1 1)); 展开 (fib 3) ，由于(fib 2) (fib 1) 结果为 1，替换
(+ (+ (+ 1 1) 1) 2); 全部转为具体的数字计算
(+ (+ 2 1) 2)
(+ 3 2)
5; 累加结果为 5

此种递归展开结构类似三角形

5.3 - countdown model

(define (countdown n)(if (= n 0)null(begin (display n) (newline)(countdown (- n 1)))))

(countdown 4)
(countdown 3)
(countdown 2)
(countdown 1)
(countdown 0)
()

it’s a kind of uni-function，执行时 countdown 得到的形式类似单一函数

6. Tail call optimisation 尾调用优化

一般语言调用递归时 每次都会产生一个栈帧 (stack frame)，在 scheme 中

• The previous stack frame is no longer needed 前一个栈帧不再需要，当我们计算 (countdown 3) 时，我们不需要前一个栈帧 (countdown 4) 的任何信息
• Throw it away 这时我们就可以将其丢弃掉

7. Iterative forms 迭代形式

7.1 - my-map model

(define (my-map fn lst)(if (null? lst)null(cons (fn (car lst))(my-map fn (cdr lst)))))

(my-map abs (list 2 -3 4)); 调用 my-map 展开 会创建一个点对，car 为对列表第一个元素应用 abs  
(cons (abs 2) (my-map abs (list -3 4))); 继续对剩余更少的元素进行 my-map
(cons 2 (cons (abs -3) (my-map abs (list 4)))); (abs 2) 的结果为 2
(cons 2 (cons 3 (cons (abs 4) (my-map abs null)))); (abs -3) 的结果为 3
(cons 2 (cons 3 (cons 4 null))); (my-map abs null) 会返回 null 
(cons 2 (cons 3 (list 4))); 根据之前的章节，这里会产生一个 list 
(cons 2 (list 3 4)); 继续合并为 (list 3 4)
(list 2 3 4)

the “shape” of my-map is again a kind of triangular form，my-map 的展开形式仍然是一种三角形格式

7.2 - iterative forms - fact

让我们尝试以不同的方式实现 fact ，为了避免这种三角形形式

(define (fact-it n)(define (impl acc count)(if (= 0 count)acc(impl (* count acc) (- count 1))))(impl 1 n))

acc 这里的意思为 accumulate 累计，上述代码中为累乘的结果，初值为 1 ，依次累乘 n，n-1，… 1
类似的 C++ 代码 (untested) 可以写作：

int fact_it(int n)
{auto impl = [](int acc, int count)-> int{ if (0 == count) return acc;else return impl(count*acc, count-1);};return imp(1,n);
}

> (fact-it 3)
; 6
> (fact-it 4)
; 24
> (fact-it 5)
; 120

让我们看一下它的形式 (Shape)

(fact-it 3)
(impl 1 3)
(impl (* 3 1) (- 3 1))
(impl 3 2)
(impl (* 2 3) (- 2 1))
(impl 6 1)
(impl (* 1 6) (- 1 1))
(impl 6 0); 此时 count 为 0 ，返回 acc 即 6
6

7.3 - Iterative forms - fib

让我们看一下如何以同样的方式实现 fib

(define (fib-it n)(define (impl acc1 acc2 count)(if (= count 2)acc1(impl (+ acc1 acc2) acc1 (- count 1))))(impl 1 1 n)) ; 函数实际的函数体

acc1 acc2 为两个累加

> (fib-it 2)
; 1
> (fib-it 3)
; 2
> (fib-it 4)
; 3
> (fib-it 5)
; 5

(fib-it 5)
(impl (+ 1 1) 1 (- 5 1))
(impl 2 1 4)
(impl (+ 2 1) 2 (- 4 1))
(impl 3 2 3)
(impl (+ 3 2) 3 (- 3 1))
(impl 5 3 2); 当 n 为 2 时返回 acc1 即 5
5

此种形式的展开均为独立的计算，并不基于前一次的计算结果

我们可以以同样的方式优化 map 吗？

• No, but “Tail call optimisation modulo cons” 不行，但是尾调用优化以 cons 为模块

---

原视频地址: https://www.bilibili.com/video/BV1Kt411R7Wf?p=4&spm_id_from=pageDriver