重学操作系统（三）
前言
之前面试遇到了递归转非递归的问题，当时把我难住了。今天就看到了相关的文章，悔不当初，应该早点看。现在就把这个文章总结下，加深记忆。
贯穿全文的问题：不支持递归的程序语言如何实现递归
for循环执行
int sum = 0;
for (int i = 1; i <= 100; i++) {
sum += i;
}
上面代码很简单，就是通过for循环，获得1 - 100相加和。但是如果是计算机指令执行，就比上述代码复杂很多，大体比如：
# var i = 1, s = 0
# 对应 Java 代码，我们首先将 1 和 0 存储到两个地址
# 这两个地址我们用 $i 和 $s 表示
store #1 -> $i // 将数字 1 存入i的地址
store #0 -> $s // 将数字 0 存入 s 的地址
# 接下来循环要开始了，我们在这里预留一个 loop 标签
# loop 是一个自定义标签，它代表指令的相对位置
# 后续我们可以用 jump 指令跳转回这个位置实现循环
loop: # 循环标签
# for ... i <= 100
# 接下来我们开始实现循环控制
# 我们先首先 i <= 100的比较
# 我们先将变量 i 的地址，也就是 $i 导入寄存器 R0
load $i -> R0
# 然后我们用 cmp 比较指令 R0 和数字 100
cmp R0 #100 // 比较 R0 和数字 100
# 注意指令不会有返回值，它会进行计算，然后改变机器的状态（也就是寄存器）
# 比较后，有几个特殊的寄存器会保存比较结果
# 然后我们用 ja（jump above）, 如果比较结果 R0 比 100 大
# 那么我们就跳转到 end 标签，实现循环的跳出
ja end
nop
# 如果 R0<=100，那么ja end 没有生效，这时我们处理 s+=i
# 首先我们把变量 s 所在地址的数据导入寄存器 R1
load $s -> R1
# 然后我们把寄存器R0和R1加和，把结果存储寄存器 R2
add R0 R1 R2
# 这时，我们把寄存器 R2 的值存入变量 s 所在的地址
store R2 -> $s
# 刚才我们完成了一次循环
# 我们还需要维护变量 i 的自增
# 现在 i 的值在 R0 中，我们首先将整数 1 叠加到 R0 上
add R0 #1 R0
# 再把 R0 的值存入i所在的内存地址
store R0 -> $i
# 这时我们的循环体已经全部执行完成，我们需要调转回上面 loop 标签所在的位置
# 继续循环
jump loop
nop
end:
其实上述就可以看作一种汇编语言，我没学过汇编，但是学过C语言，感觉编写逻辑也是和上述类似的。通过上述方式，上面的for循环操作成功转换成指令，然后在编码成二进制，就能存在内存中了。
条件控制程序
主要是if-else和switch-case，if-else是自上向下执行，所以如果有1000个case，最坏结果是执行999次。而switch-case是可以通过数学方法，精确定位到相应的case。
函数
函数的执行，深入到底层，涉及到栈这种数据结构。比如下面这个两数相加的方法：
int add(int a, int b) {
return a + b;
}
在上述例子中，栈的主要作用是解决两个问题，一是参数如何传递给函数，而是返回值如何传递给调用者。
因此上述方法执行顺序是：
调用 -> 参数压栈 -> Stack -> 取出参数 -> 函数执行
上述方法返回结果顺序是：
函数执行 -> 写入结果，参数出zhan -> Stack -> 取出结果 -> 调用
参数入栈叫做压栈，结果取出叫做出栈。栈中每个数据大小一样，所以函数执行中，我们通过参数个数和参数的序号计算参数在栈中的位置。
例如执行11 + 15:
1. 压栈参数11
2. 压栈15
3. 返回值压栈（这时候是0）
4. 调用函数，结果写入返回值
5. 存储函数调用前存储的指针，方便函数结束后，跳转回去
6. 函数参数和返回值换位置，清除，这样就从参数先清除，不会出现异常
递归的执行
给出一个递归的例子：
int sum(int n) {
if (n == 1) return 1;
return n + sum(n - 1);
}
递归的时候，每次执行，都会形成一个参数 -> 返回地址 -> 返回值这样的栈结构。比如sum（1000）第一次调用n，第二次调用99。这样的话，栈会非常大。消耗了更多的空间，但是保证一定的独立性。递归需要退出条件，不然就会死循环。因为递归和栈存取数据方式类似，因此栈是实现递归的一种方式。而大部分编程语言，是用栈来实现递归的。
类型（class）的实现
总结前面的：
- 变量是一个内存地址，只需要分配内存就好（指针）
- 循环控制：跳转➕判断
- 条件控制：跳转➕判断，switch-case需要一些数学计算
- 函数：参数压栈，结果出栈，返回值，返回地址
那么，class是如何被指令实现的？
class可以分为两部分，一部分是属性，另一部分是方法。而class有一个特殊的函数叫构造函数，它会为class分配内存。构造函数执行时，扫描class中定义的所有属性和方法。
- 遇到属性，为属性分配内存地址
- 遇到方法，方法本身存到程序所在内存区域，方法的值设置为方法指令所在的内存地址
当调用一个class的方法时候，本质是执行了一个函数，和函数调用一致：
- 返回值返回地址压栈
- 参数压栈
- 执行跳转
this指针的实现
把this作为函数的第一个参数压栈，这样class的函数就能访问class的成员了。
总结
- 将程序编译成指令 - 编译器
- 图灵完备语言：一个语言的能力和图灵机等价，也就是说，平时编程做的事，指令也能做到，所以计算能力等价。也就是一种编程语言的能力，与图灵机等价，称为图灵完备语言。
贯穿全文的问题 =》不支持递归的程序语言如何实现递归？
- 我们需要一个栈（数组就可以）
- 我们需要一个栈指针，或者类似Java这种，用变量
- 然后实现压栈出栈等操作
斐波那契求第n项：
int fib(int n) {
if(n == 1 || n == 2) { return n; }
return fib(n-1) + fib(n-2)
}
改写为非递归：
private static int fib2(int n) {
if (n == 1 || n == 2) {
return n;
}
//初始化数据
int[] stack = new int[n];
int point = n - 3;
stack[n - 1] = 1;
stack[n - 2] = 2;
//数组模拟出栈入栈
while (point >0) {
stack[point] = stack[point + 1] + stack[point + 2];
point--;
}
return stack[0];
}
