不支持递归的程序语言如何实现递归程序
为了弄清楚这道题目，你需要对程序有一个更深层次的认识，不仅仅停留在指令的执行层面，而是要灵活使用指令，去实现更加复杂的功能。
for 循环如何被执行
var i = 1, s = 0;
for(; i <= 100; i++) {
s+=i;
}
因为 for 循环可以执行 1 次，也可以执行 100W 次，还可以执行无数次。因此，指令的设计者提供了一种 jump 类型的指令，让你可以在程序间跳跃，比如:
loop:
jump loop
用这种方法，我们可以将 for 循环用底层的指令实现：
# 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:
通过上面的方法，我们成功将 for 循环的程序转换成了指令，然后再将它们编码成二进制，就可以存储到内存中了。
几个要点：
1.jump 指令直接操作 PC 指针，但是很多 CPU 会抢先执行下一条指令，因此通常我们在 jump 后面要跟随一条 nop 指令，让 CPU 空转一个周期，避免 jump 下面的指令被执行。
2.上面 add/store 这些指令，它们叫作助记符，是帮助你记忆的。整体这段程序，我们就称作汇编程序。不同的机器助记符也不一样，不用去记忆这些指令。当你拿到指定芯片的时候，直接去查阅芯片的说明书就可以了。
3.虽然不同 CPU 的指令不一样，但也是有行业标准的。现在使用比较多的是 RISC（精简指令集）和 CISC（复杂指令集）。比如目前Inte 和 AMD 家族主要使用 CISC 指令集，ARM 和 MIPS 等主要使用RISC 指令集。
条件控制程序
条件控制程序有两种典型代表，一种是 if-else ，另一种是 switch-case 。 总体来说， if-else 翻译成指令，是比较简单的，你需要用跳转指令和比较指令处理它的跳转逻辑。
当然，它们的使用场景不同，这块我不展开了。在这里我主要想跟你说说，它们的内部实现是不一样的。if-else 是一个自上向下的执行逻辑， switch-case是一种精确匹配算法。比如你有 1000 个 case，如果用 if-else 你需要一个个比较，最坏情况下需要比较 999 次；而如果用 switch-case ，就不需要一个个比较，通过算法就可以直接定位到对应的case 。
举个具体的例子，比如一个根据数字返回星期的程序。如果用if-else，那么你需要这样做：
if(week == 1) {
return "周一";
} else if(week == 2) {
return "周二";
}
如果用 switch-case 的逻辑，你可能会这样计算：
跳转位置=当前PC + 4*(week * 2 - 1)
** switch-case 实现更多是依赖数学关系，直接算出 case 所在指令的位置，而不是一行行执行和比较。指针每次移动或扩容都会走4个字节，为了根据周的匹配所以才有上述公式,这里只是其中一种算法**
函数
了解了循环和条件判断，我们再来看看函数是如何被执行的。函数的执行过程必须深入到底层，也会涉及一种叫作栈的数据结构。
下面是一段 C 程序，传入两个参数，然后返回两个参数的和：
int add(int a, int b){
return a + b;
}
上面函数进行了a+b的运算，我们可以这样构造指令：
# 首先我们定义一个叫作add的标签
add:
# 然后我们将a和b所在地址中的数据都导入寄存器
load $a -> R0
load $b -> R1
# 然后我们将寄存器求和，并将结果回写到返回地址
add R0 R1 R2
store R2 -> $r
当我们需要调用这个函数的时候，我们就构造下面这样的指令：
jump add
这里有 2 个问题还没有解决：
1.参数如何传递给函数？
2.返回值如何传递给调用者？
为了解决这 2 个问题，我们就需要用到一个叫作栈的数据结构。栈的英文是 Stack，意思是码放整齐的一堆东西。首先在调用方，我们将参数传递给栈；然后在函数执行过程中，我们从栈中取出参数。
函数执行过程中，先将执行结果写入栈中，然后在返回前把之前压入的参数出栈，调用方再从栈中取出执行结果。
将参数传递给 Stack 的过程，叫作压栈。取出结果的过程，叫作出栈。栈就好像你书桌上的一摞书，压栈就是把参数放到书上面，出栈就是把顶部的书拿下来。
因为栈中的每个数据大小都一样，所以在函数执行的过程中，我们可以通过参数的个数和参数的序号去计算参数在栈中的位置。
接下来我们来看看函数执行的整体过程：假设要计算 11 和 15 的和，我们首先在内存中开辟一块单独的空间，也就是栈。
栈的使用方法是不断往上堆数据，所以需要一个栈指针（Stack Pointer， SP）指向栈顶（也就是下一个可以写入的位置）。每次将数据写入栈时，就把数据写到栈指针指向的位置，然后将 SP 的值增加。
为了提高效率，我们通常会用一个特殊的寄存器来存储栈指针，这个寄存器就叫作 Stack Pointer，在大多数芯片中都有这个特殊的寄存器。一开始，SP 指向 0x100 位置，而 0x100 位置还没有数据。
压栈参数11
接下来我们开始传参，我们先将 11 压栈，之所以称作压栈（ Push)，就好像我们把数据 11 堆在内存中一样。模拟压栈的过程是下面两条指令：
store #11 -> $SP // 将11存入SP指向的地址0x100
add SP, 4, SP // 栈指针增加4（32位机器）
第一条 store 指令将 SP 寄存器指向的内存地址设置为常数 11。
第二条指令将栈指针自增 4。
这里用美元符号代表将 11 存入的是 SP 寄存器指向的内存地址，这是一次间接寻址。存入后，栈指针不是自增 1 而是自增了 4，因为我在这里用的是一个 32 位宽的 CPU 。如果是 64 位宽的 CPU，那么栈指针就需要自增 8。
压栈参数15
然后我们用同样的方法将参数 15 压栈。
接下来，我们将返回值压栈。
当我们完成了上面的压栈后，就开始调用函数，一种简单的做法是用 jump 指令直接跳转到函数的标签，比如：
jump add
这个时候，要加和在栈中的数据 11 和 15，我们可以利用 SP 指针寻找数据。11 距离当前 SP 指针差 3 个位置，15 距离 SP 指针差 2 个位置。这种寻址方式是一种复合的寻址方式，是间接 + 偏移量寻址。
我们可以用下面的代码完成将 11 和 15 导入寄存器的过程：
load $(SP - 12) -> R0
load $(SP - 8) -> R1
然后进行加和，将结果存入 R2。
load R0 R1 R2
最后我们可以再次利用数学关系将结果写入返回值所在的位置
store R2 -> $(SP-4)
一个好的解决方案，也会面临问题。现在我们就遇到了麻烦：
函数计算完成，这时应该跳转回去。可是我们没有记录函数调用前 PC 指针的位置，因此这里需要改进，我们需要存储函数调用前的 PC 指针方便调用后恢复。
栈不可以被无限使用，11和 15 作为参数，计算出了结果 26，那么它们就可以清空了。如果用调整栈指针的方式去清空，我们就会先清空 26。此时就会出现顺序问题，因此我们需要调整压栈的顺序。
然后我们在调用函数前，还需要将返回地址压栈。这样在函数计算完成前，就能跳转回对应的返回地址。翻译成指令，就是下面这样：
## 压栈返回值
add SP, 4 -> SP
# 计算返回地址
# 我们需要跳转到清理堆栈那行，也就是16行
MOV PC+4*(参数个数*2+1) -> SP
# 压栈参数的程序
……
# 执行函数，计算返回值
call function
# 清理堆栈
add SP, -(参数个数+1)*4， SP
递归函数如何被执行
int sum(int n){
if(n == 1) {return 1;}
return n + sum(n-1);
}
比如执行 sum(100)，我们就会形成一个复杂的栈，第一次调用 n = 100，第二次递归调用 n = 99,它们堆在了一起，就形成了一个很大的栈,递归消耗了更多空间，但是也保证了中间计算的独立性。
类型（class）如何实现
首先一个 class 会分成两个部分，一部分是数据（也称作属性），另一部分是函数（也称作方法）。
class 有一个特殊的方法叫作构造函数，它会为 class 分配内存。构造函数执行的时候，开始扫描类型定义中所有的属性和方法。
-如果遇到属性，就为属性分配内存地址；
-如果遇到方法，方法本身需要存到正文段（也就是程序所在的内存区域），再将方法的值设置为方法指令所在的内存地址。
当我们调用一个 class 方法的时候，本质上是执行了一个函数，因此和函数调用是一致的：
1.首先把返回值和返回地址压栈；
2.然后压栈参数；
3,最后执行跳转。
这里有一个小问题，有时候 class 的方法会用到this ，这其实并不复杂，你仔细想想， this指针不就是构造函数创建的一个指向 class 实例的地址吗？那么，有一种简单的实现，就是我们可以把 this 作为函数的第一个参数压栈。这样，类型的函数就可以访问类型的成员了，而类型也就可以翻译成指令了。
一个程序语言如果不支持递归函数的话，该如何实现递归算法？
1.我们需要用到一个栈（其实用数组就可以）；
2.我们还需要一个栈指针，支持寄存器的编程语言能够直接用寄存器，而不支持直接用寄存器的编程语言，比如 Java，我们可以用一个变量；
3.然后我们可以实现压栈、出栈的操作，并按照上面学习的函数调用方法操作我们的栈。
网友评论