递归比循环更快吗？

第一个概念： 内存单元，存储，状态 。 要做某些事情，您需要存储最终和中间结果值的位置。 我们假设我们有一个无限数组的“整数”单元，称为存储器 ，M [0..Infinite]。

说明：做点事 - 改造一个细胞，改变它的价值。 改变状态 。 每个有趣的指令都会进行转换。 基本说明是：

a） 设置并移动内存单元

执行代理 ：现代CPU中的核心。 “代理”是可以执行指令的东西。 代理也可以是一个人在纸上遵循算法。

步骤顺序：一系列指令 ：即：先执行此操作，然后执行此操作，等等。一系列必要的指令。 即使是一行表达式也是“一个必要的指令序列”。 如果你有一个特定的“评估顺序”表达式，那么你有步骤 。 这意味着即使单个组合表达式具有隐含的“步骤”，并且也具有隐式局部变量（我们称之为“结果”）。 例如：

4 + 3 * 2 - 5
(- (+ (* 3 2) 4 ) 5)
(sub (add (mul 3 2) 4 ) 5)  

上面的表达意味着隐含“结果”变量的3个步骤。

// pseudocode

       1. result = (mul 3 2)
       2. result = (add 4 result)
       3. result = (sub result 5)

所以，即使中缀表达式，因为你有一个特定的评估顺序，所以它是一系列必要的指令。 表达式意味着要按特定顺序进行的一系列操作，并且由于有步骤，所以还有一个隐含的“结果”中间变量。

指令指针 ：如果你有一系列步骤，你也有一个隐含的“指令指针”。 指令指针标记下一条指令，并在指令读取之后但执行指令之前前进。

在这个伪计算机中，指令指针是存储器的一部分。 （注意：通常指令指针是CPU核心中的“特殊寄存器”，但这里我们将简化概念并假定所有数据（包含寄存器）都是“存储器”的一部分）

跳转 - 一旦你有一个有序的步数和一个指令指针，你可以应用“ 存储 ”指令来改变指令指针本身的值。 我们将用一个新的名称来调用这个存储指令的具体用法： 跳转 。 我们使用一个新的名字，因为它更容易被认为是一个新概念。 通过更改指令指针，我们正在指示代理“转到步骤x”。

无限迭代 ：通过跳回，现在可以让代理“重复”一定数量的步骤。 此时我们有无限的迭代。

                   1. mov 1000 m[30]
                   2. sub m[30] 1
                   3. jmp-to 2  // infinite loop

有条件的 - 有条件地执行指令。 使用“条件”子句，可以根据当前状态（可以使用前一条指令设置）有条件地执行几条指令之一。

适当的迭代 ：现在使用条件子句，我们可以避开跳回指令的无限循环。 我们现在有一个条件循环 ，然后进行适当的迭代

1. mov 1000 m[30]
2. sub m[30] 1
3. (if not-zero) jump 2  // jump only if the previous 
                        // sub instruction did not result in 0

// this loop will be repeated 1000 times
// here we have proper ***iteration***, a conditional loop.

命名 ：将名称命名为保存数据或保存步骤的特定内存位置。 这只是一种“便利”。 我们不会添加任何新的说明，因为有能力为内存位置定义“名称”。 “命名”不是代理人的指令，这对我们来说只是一种方便。 命名使代码（此时）更易于阅读并且更易于更改。

   #define counter m[30]   // name a memory location
   mov 1000 counter
loop:                      // name a instruction pointer location
    sub counter 1
    (if not-zero) jmp-to loop  

一级子程序 ：假设您需要频繁执行一系列步骤。 您可以将步骤存储在内存中的指定位置，然后在需要执行它们（调用）时跳转到该位置。 在序列结束时，您需要返回到调用点以继续执行。 有了这个机制，你就可以通过编写核心指令来创建新的指令（子程序）。

实施:(不需要新的概念）

堆栈 ：你可以定义一个内存空间作为一个“堆栈”，你可以在堆栈上“推送”值，也可以“弹出”最后一个“推送”的值。 要实现一个堆栈，你需要一个堆栈指针 （类似于指令指针），它指向堆栈的实际“头部”。 当你“推”一个值时，堆栈指针递减并且存储该值。 当你“弹出”时，你得到实际堆栈指针的值，然后堆栈指针递增。

子程序现在我们有了一个堆栈，我们可以实现允许嵌套调用的正确的子程序。 这个实现类似，但不是将指令指针存储在预定义的存储位置，而是将IP的值“推”到堆栈中。 在子程序结束时，我们只是“弹出”栈中的值，在原始调用之后有效地跳回到指令。 这个具有“堆栈”的实现允许从另一个子例程调用一个子例程。 通过这个实现，我们可以通过使用核心指令或其他子例程作为构建块，将新指令定义为子例程时创建多个抽象级别。

递归 ：子程序自行调用时会发生什么？ 这被称为“递归”。

问题：覆盖本地中间结果，子程序可以存储在内存中。 由于您正在调用/重复使用相同的步骤， 如果中间结果存储在预定义的内存位置（全局变量）中，它们将在嵌套调用中被覆盖。

解决方案：为了允许递归，子例程应该将本地中间结果存储在堆栈中 ，因此，在每次递归调用（直接或间接）时，中间结果都存储在不同的存储器位置。

当你处理简单的，顺序的数据结构时，你应该使用“迭代”，并且在“简单循环”的任何地方都应该使用“迭代”。

当需要处理递归数据结构（我喜欢称它们为“分形数据结构”）时，或者当递归解决方案明显更“优雅”时，应该使用“递归”。