函数: 代码的组织形式

最初的编程语言是没有函数的，当然现在编写程序也可以完全不使用函数(直接一个 main 梭哈到底)也可以，但是使用函数编写程序能够更方便的理解和重复使用。

函数的作用

把代码切分为多个函数，如同将一个大型的组织按照部门划分开。

在一个小的程序里，函数就没有多大意义。就像没必要将几个关系融洽的人组成的公司强行拆分为部门。但是人一旦多起来就需要使用财务部、开发组等来区分部门了，程序也不例外。

程序就像玩具，将小的零件组成一个大的零件，最终组成玩具。程序中的零件就是函数。

就像玩具需要螺丝钉，而且需要大量的螺丝钉。这些小的重复的组件就能够通过规范来要求来作为一个整体提供。而这也就是函数的意义，他将语句通过函数提供，只需要简单的调用就能够实现特定的功能。

函数的演化

最初是没有函数的，但是随着程序复杂性就自然而然出现了函数的需求，因此就需要通过现有的技术来构建，直到有人归纳发明新的语言特性。

goto: 实现部分函数功能

我们知道 goto 能够实现程序的跳转，因此我们只需要在需要调用函数的时候通过 goto 跳转到函数标签上即可:

上图就是利用函数的方式，但是goto 有个巨大的问题就是它无法将程序返回到原来的位置。

因此要想实现真正的函数运行需要满足两个方面:

1. 程序执行流程跳转到函数所在位置(goto 可以满足)
2. 函数执行后跳转回原来的执行位置(goto 无法满足)

函数的诞生: 动态修改 goto 跳转

最初的程序命令和数据都是存储在内存中的，修改程序本身就像数值传入变量一样的简单。因此通过直接修改程序中跳转命令的跳转目的地就能够使函数在调用后返回原来的位置。

Text Only

1. 将 110 处跳转命令的跳转目的地修改为 3
2. 调用函数(跳转至 100)
3. 调用函数后需要执行的语句
...
51. 将 110 处跳转命令的跳转目的地修改为 53
52. 调用函数(跳转至 100)
53. 调用函数后需要执行的语句
...
100. 函数
...
110. 函数返回(默认跳转为 0)，他们能够在程序中被修改

即在编写程序时，每次函数调用前都需要修改下函数返回(110)处的跳转目标。因为在函数编写时我们已经知道了函数返回的地址。

但是这种方式有一个非常大的问题就是，函数调用者必须细心的维护这个地址。并且每次源码改变，例如在函数中增加了几行代码，返回命令的位置就会变动，整个代码所有调用函数处也需要相应的修改。

专用内存: 记录跳转目的地

由于动态修改对人的心智造成的负担就想到了使用一个专有内存来保持跳转目的地:

Text Only

1. 将 3 写入目的地内存
2. 调用函数(跳转到 100 处)
3. 调用函数后需要执行的语句
...
100. 函数
...
110. 跳转到目的地内存所记录的地址

然而这种方法也有一个问题，当调用函数 X 期间又调用了函数 Y 时，返回目的地内存被写覆盖。函数 X 在执行之后获取的目的地地址就是错误的了(Y 函数保存的)。

这就需要开辟一个新的内存空间，来保存函数调用时应当返回的目的地地址，他们还应该与函数一一对应, 于是栈出现了。

栈: 记录函数执行链上的跳转

最终栈终于登场了。它是一种存储多值的容器型数据结构，特点是 LIFO 即后存入的先读取。

栈在内存中是连续的，我么首先需要一个特定内存(rsp寄存器)来记录目前栈顶的位置，这样随着程序的执行不断执行压栈和出栈操作并更新栈顶的位置即可。

上图就是整个压栈的流程:

Text Only

# 初始
42. 保存栈顶 -> 100
100. null
...
# 调用函数时将函数的返回目的地(也就是调用函数的下一条语句对应的地址)压入栈顶
32. 保存栈顶 -> 101
...
101. 函数 X 的返回目的地

# 以此类推每次函数调用都压入栈

而栈的读取刚好相反:

Text Only

42. 保存栈顶 -> 102
...
100. null
101. 函数 X 的返回目的地
102. 函数 Y 的返回目的地

# Y 函数执行完毕，从栈顶执行出栈
# 102 出栈获取 Y 函数返回目的地，栈顶移动到 101
42. 保存栈顶 -> 101
100. null
101. 函数 X 的返回目的地

用栈结构来保存函数调用时应当返回的目的地地址是目前编程语言的主流方式。

递归调用

所谓的递归调用就是函数内部再次调用当前函数的过程。简单的总结下递归实现需要满足的条件:

1. 一个问题可以分解为几个问题的解(函数的基本思想)
2. 该问题分解之后的至问题，除了数据规模不同，求解思路是完全一样的
3. 存在递归终止的条件

递归调用并不是不可或缺的，理论上可以通过自己实现栈结构就可以重构他。但是对于一些特定的逻辑使用递归会非常好理解。

线性递归

我们以阶乘为例，他的定义方式是 n! = n*(n-1)*(n-2)...3*2*1。如果用递归思维它能够分为 n! = n * (n-1)! 这样的形式:

Common Lisp

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

例如我们计算 6! 他的执行路径:

Text Only

(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

这种递归方式属于线性递归，线性递归的最后一步操作不是递归操作，将最终条件代入计算，通俗讲就是下一次的递归作为当前递归的参数，这意味着每次函数调用都需要保存整个调用栈(是所有的，例如 n 次调用需要保存 n 次 factorial1，n-1 次 factorial2 以此类推)，这就会导致栈溢出。

即线性递归的栈使用是指数递增的

线性迭代(尾递归)

线性递归的栈指数递增是一个非常大的问题，为了优化这个问题需要在进行递归之前，把全部的操作先执行完毕，这也让的好处就是栈中不需要花费大量的栈空间来保存上次递归中的参数、局部变量等信息，只需要保存递归内函数调用的返回地址。

Common Lisp

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
    product
    (fact-iter (* counter product)
                (+ counter 1)
                max-count)))

可以看到，递归的 fact-iter 函数中的参数都不是递归函数本身，他的函数执行路径:

Text Only

(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

可以看到整个函数执行路径中要保存的轨迹所有的东西都是 product counter 和 max-count 的当前值，而不是整个递归函数的调用栈。这个过程被称为线性迭代，也称为尾递归。他的整个栈使用是线性递增的。

还有所有尾递归理论上都能够使用循环来实现。一些编译器也能够自动将线性递归优化为尾递归。

树形递归

还有一种常见的递归模式是树形递归，例如斐波那契数列，他的基本规则:

Text Only

          0                     如果 n = 0
Fib(n) =  1                     如果 n = 1
          Fib(n-1) + Fib(n-2)   否则

根据基本规则能够看出他非常符合递归的条件:

Common Lisp

(define (fib n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib (-n 1))
                    (fib (-n 2))))))

他的每层分裂为两个分支:

当然上面的计算方式是最直观，但是也是最糟糕的方式了。每个计算都要保存两个函数的调用栈，做了太多的冗余计算了，更好的方式:

Common Lisp

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
    b
    (fib-iter (+ a b) a (- count 1))))

又换算成了尾部递归。

所谓的尾递归化就是将原本使用递归函数作为参数的通过几个状态量来直接返回函数本身。

高阶函数

函数是一种比表达式更高层次的抽象，他描述了对数的一种复合操作，而又不依赖于特定的数:

Common Lisp

(* 3 3 3) ; 表达式，智能计算 3^3
(define (cube x) (* x x x))  ;函数，不依赖于 3 能够计算所有的 x^3

如果参数只能是数，他就严重限制了我们建立进一步抽象的能力:

Common Lisp

# a 到 b 的各整数之和: a + (a+1) ... b
(define (sum-integers a b)
  (if (> a b)
    0
    (+ a (sum-integers (+ a 1) b))))

# a 到 b 的整数的立方之和: a^2 + (a+1)^2 ... b^2
(define (sum-cubes a b)
  (if (> a b)
    0
    (+ (cube a) (sum-cubes (+ a 1) b))))

上面是两个函数共享着一种公共的基础模式，大部分都是共同的，但是他们需要两个函数来实现。为了对他进行抽象，需要构造这个特殊函数来作为参数，或者以函数作为返回值。这类参数是函数或返回值是函数的被称为高阶函数。

Common Lisp

(define (sum term a b)
  (if (> a b)
    0
    (+ (term a)
      (sum (+ a 1) b))))

其中 term 就必须是一个函数:

Common Lisp

(define (identity x) x)
(sum identity 1 10)  # 55
(sum cube 1 10)

由于他们必须是一个函数，而即使是接受一个字面量的也需要一个函数例如 identity。这样非常简单的函数也需要 define 就非常的傻，因支持高阶函数的语言都会提供了一个 lambda 的特殊形式:

Common Lisp

(sum (lambda (x) (x)) 1 10) # 55

# (lambda (parameters) (body))

lambda 是一个表达式，他不需要函数名