递归很有趣。然而,在安全关键应用中,它被视为一件危险的事情(因为可能会导致堆栈溢出?)。
想象一下,如果您需要处理您喜欢的语言的子集,但不允许使用递归——那对您来说是否是一场灾难?
正式问题:对于每个递归函数,都可以创建一个完全等效的非递归函数吗?这是真的吗?还是有关于此的定理或其他东西?
递归很有趣。然而,在安全关键应用中,它被视为一件危险的事情(因为可能会导致堆栈溢出?)。
想象一下,如果您需要处理您喜欢的语言的子集,但不允许使用递归——那对您来说是否是一场灾难?
正式问题:对于每个递归函数,都可以创建一个完全等效的非递归函数吗?这是真的吗?还是有关于此的定理或其他东西?
是的,每个这样的函数都可以被重写为一个非递归函数。我不确定是否有一种正式的方法来做到这一点,但它在文献中被称为“递归展开”或“递归展开”。
在大多数情况下,应避免使用递归。特别是在所提到的那种系统中,例如MISRA-C禁止使用递归。
有一些罕见的情况下,递归很方便并使代码更有效率,例如一些二叉树的实现等。
但递归的主要目的是将其教给困惑的学生,以便当他们变得经验丰富时,他们可以将其教给困惑的学生,以便-...:)
递归不是免费的
它需要相当数量的内存空间(通常在堆栈上)
和CPU时间(通过调用、重建堆栈框架等)。
在紧密循环中,这使得递归算法比其非递归等效算法慢。
如果速度和堆栈限制不是问题,那么请保留递归,但如果您在紧密循环中使用递归(这经常是情况),
通过消除递归,您可以获得很多优化选项。
因为:也许:
1. 您不需要保存所有这些寄存器/变量
2. 您不必跳回到从哪里来的确切位置。
3. 您不需要为每个递归调用那个清理代码
4. 您可以展开一些循环
5. 您可以在那个非递归程序上使用inline
指令。
我对递归的主要问题是它最常用于的数据结构:树。
树需要指针,而指针需要随机内存访问(它们跳来跳去),这对缓存使用不利,因为顺序访问比随机访问快得多。Example of a binary tree stored in an array
+-----------------+
|0eeeeeeeeeeeeeeee| //no pointers needed, parent/child, is y dimension,
|11 dddddddd| //sibbling is x dimension of the array.
|2222 cccc| //The 123 tree is stored root up.
|33333333 bb| //Notice how the abc-tree is stored upside down
|4444444444444444a| //The wasted space in the middle, is offset by the fact
+-----------------+ //that you do not need up, down, and sibbling pointers.