循环不变量_Code

相关文章推荐

单身的拐杖 · 如何写注册表文件-CSDN博客· 4 月前 ·

健壮的香烟 · flume系列之：使用通配符批量消费kafk ...· 5 月前 ·

冷静的猴子 · 万顺叫车被指涉嫌传销 ...· 6 月前 ·

欢快的冰淇淋 · 矩阵的秩· 7 月前 ·

高大的铁板烧 · 如何用 PYTHON 绘制漂亮的地图？— ...· 1 年前 ·

由于循环和递归的程序相似的原因，证明带有不变量的循环的部分正确性和证明通过归纳的递归程序的正确性极其相似。事实上，循环不变量通常是一个递归程序可以等价为一个给定循环的递归的属性。 ^{循环不变代码外提

（英语：loop-invariant code motion，缩写LICM）在计算机编程中是指将循环不变的语句或表达式移到循环体之外，而不改变程序的语义。循环不变代码外提在英文中又被称为hoisting或scalar promotion，是

编译器

中常见的

优化

方法。
^{在计算机科学中，

循环不变性

（loop invariant，或“循环不变量”），是一组在循环体内、每次迭代均保持为真的性质，通常被用来证明

程式

或

伪码

的正确性（有时但较少情况下用以证明

算法

的正确性）。简单说来，“循环不变性”是指在循环开始和循环中，每一次迭代时为真的性质。这意味着，一个正确的循环体，在循环结束时“循环不变性”和“循环终止条件”必须同时成立。

由于

循环

和递归的相通，证明带有不变性的循环的部分正确性和证明通过归纳的递归程序的正确性极其相似。
^{递归

（英语：Recursion），又译为

递回

，在

数学

与计算机科学中，是指在

函数

的定义中使用函数自身的方法。递归一词还较常用于描述以

自相似

方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

归经常被用于解决计算机科学的问题。在一些编程语言（如

Scheme

、

Haskell

中），递归是进行

循环

的一种方法。
^{C. A. R. Hoare. "An axiomatic basis for computer programming". Communications of the ACM, 12(10):576–585, October 1969. doi:10.1145/363235.363259

Stokey, Nancy,; Robert Lucas; Edward Prescott. Recursive Methods in Economic Dynamics. Harvard University Press. 1989. ISBN 0674750969.}}}}