在 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
