在 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;
else
return 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