递归

编辑
本词条由“匿名用户” 建档。

递归(形容词:递归)发生在根据自身或其类型定义事物时。递归用于从语言学到逻辑学的各种学科。递归最常见的应用是在数学和计算机科学中,其中定义的函数在其自己的定义中应用。虽然这显然定义了无限数量的实例(函数值),但它通常以不会发生无限循环或无限引用链(crock递归)的方式完成。 在数学和计算机科学中,一类对象或方法在可以由两个属性定义时表现出递归行为: 一个简单的基本案例(或多个案例)——一个不使用...

递归

编辑

递归(形容词:递归)发生在根据自身或其类型定义事物时。 递归用于从语言学到逻辑学的各种学科。 递归最常见的应用是在数学和计算机科学中,其中定义的函数在其自己的定义中应用。 虽然这显然定义了无限数量的实例(函数值),但它通常以不会发生无限循环或无限引用链(crock 递归)的方式完成。

正式定义

编辑

在数学和计算机科学中,一类对象或方法在可以由两个属性定义时表现出递归行为:

  • 一个简单的基本案例(或多个案例)——一个不使用递归来产生答案的终止场景
  • 递归步骤 - 一组规则,可将所有连续案例减少到基本案例。

例如,下面是一个人的祖先的递归定义。 一个人的祖先是:

  • 一个人的父母(基本情况),或
  • 一个人的父母的祖先(递归步骤)。

斐波那契数列是递归的另一个经典例子:

Fib(0) = 0 作为基本情况 1,Fib(1) = 1 作为基本情况 2,对于所有整数 n >; 1, Fib(n) = Fib(n − 1) + Fib(n − 2)。

许多数学公理都基于递归规则。 例如皮亚诺公理对自然数的形式化定义可以描述为:零是一个自然数,每个自然数都有一个后继,也就是一个自然数。 通过这种基本情况和递归规则,可以生成所有自然数的集合。

其他递归定义的数学对象包括阶乘、函数(例如,递归关系)、集合(例如,康托尔三元集)和分形。

递归有各种更多的半开玩笑的定义; 参见递归幽默。

非正式定义

编辑

递归是当过程的步骤之一涉及调用过程本身时过程所经历的过程。 经过递归的过程被称为“递归的”。

要理解递归,必须认识到过程和过程的运行之间的区别。 程序是基于一组规则的一组步骤,而程序的运行涉及实际遵循规则并执行这些步骤。

递归与过程规范中对其他过程执行的引用有关,但不相同。

当这样定义过程时,这会立即产生无限循环的可能性; 如果在某些情况下跳过相关步骤以便完成过程,则递归只能在定义中正确使用。 递归有直接、间接和循环三种形式。 直接递归是函数 (A) 调用自身(A 引用 A); 间接递归发生在一个函数 (A) 调用 (B)、函数 (B) 调用函数 (C)、函数 (C) 调用 (D) 等时,直到链中的一个函数调用更早的函数。 当函数 (A) 和函数 (B) 相互调用时,就会发生循环递归。 如果在直接递归、间接递归或循环递归中出现死循环,则称其为crock递归条件。 基本上有两种方法可以防止 crock 递归,要么限制函数可以引用自身的次数,要么对函数调用的深度设置xxx限制,例如 如果深度限制为 50,则任何时候一个过程调用另一个过程时,计数器都会增加; 当它退出时,该计数器会减少。 一旦计数器达到限制(在本例中为 50),则不允许进一步的过程调用; 如果尝试调用第 51 个函数,则操作终止。 使用递归限制只能防止 crock 递归; 除了停止 crock 递归之外,设置调用限制可能会产生副作用,即阻止执行深度嵌套但不是递归的合法复杂过程。

递归

但是即使定义得当,递归过程对人类来说也不容易执行,因为它需要区分新的和旧的、部分执行的过程调用; 这需要对程序的各种同步实例的进展情况进行一些管理。 出于这个原因,递归定义在日常情况下非常少见。

语言

编辑

语言学家诺姆·乔姆斯基 (Noam Chomsky) 和其他许多人认为,一种语言中的语法句子数量没有上限,语法句子长度也没有上限(超出实际限制,例如可以说出一个句子的时间) ), 可以解释为自然语言递归的结果。

这可以根据句法类别(例如句子)的递归定义来理解。

内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/198271/

(5)
词条目录
  1. 递归
  2. 正式定义
  3. 非正式定义
  4. 语言

轻触这里

关闭目录

目录