【Scheme】Scheme 编程学习 (四) —— 递归
文章目录
【Scheme】Scheme 编程学习 (四) —— 递归
1. Factorial 阶乘
2. Fibonacci 斐波那契数列
3. Countdown 倒计时
4. Map
5. Recursion "shapes" 递归的形式
5.1 factorial model
5.2 - fibonacci model
5.3 - countdown model
6. Tail call optimisation 尾调用优化
7. Iterative forms 迭代形式
7.1 - my-map model
7.2 - iterative forms - fact
7.3 - Iterative forms - fib
在 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");