函数式编程语言

Lisp基本语法

表达式（算术运算表达式）

> (+ 1 2)
< 3
> (+ 1 2 3 4)
< 10
> (+ (* 3 3) (* 4 4))
< 25

较长的表达式（组合表达式）

(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))

(+ (* 3
        (+ (* 2 4) 
            (+ 3 5)))
    (+ (- 10 7) 
        6))  //57

命名（也叫定义，不叫赋值）

< (define size 5)
> 
< (* size 2)
> 10

复合过程（函数定义）

< (define (add a b) (+ a b))
< (add 1 2)
> 3
< (define (square x) (* x x))
< (square 4)
> 16

递归求值

求值规则

1. 求各子表达式的值（右值）
2. 将所有右值应用到运算符上就得最终结果

(* (+ 2 (* 4 6))
    (+ 3 5 7))

递归

一层一层的往下调用自己
场景：我们要实现一个1到6的阶乘，也就是65432*1
通过Lisp的写法

(define (factorial n)
    (if (= n 1)
        1
        (* n (factorial (- n 1)))))

定义一个factorial函数，参数为n，如果n等于1就返回1，否则就返回n*factorial(n-1)
也就是下面的

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720)

迭代

(factorial 6)
(fact-iter   1 1 6)
(fact-iter   1 2 6)
(fact-iter   2 3 6)
(fact-iter   6 4 6)
(fact-iter  24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

(define (factorial n)
    (fact-iter 1 1 n))
(define (fact-iter result n n-max)
    （if (> n max-n)
        result
        (fact-iter (* n result)
                    (+ n 1)
                    max-n)))

对比递归和迭代：
递归：先递进（展开），再回归（求值）。
迭代：从一个状态到下一个状态（有多个变量表示状态，每次更新这几个变量）。