递归是什么

小白 QA 2020-04-25 10:20:36 阅读(...)

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

递归是什么

递归定义

递归,就是在运行的过程中调用自己。

构成递归需具备的条件:

1. 子问题须与原始问题为同样的事,且更为简单;

2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

在数学和计算机科学中,递归指由一种(或多种)简单的基本情况定义的一类对象或方法,并规定其他所有情况都能被还原为其基本情况。

例如,下列为某人祖先的递归定义:

某人的双亲是他的祖先(基本情况)。某人祖先的双亲同样是某人的祖先(递归步骤)。斐波纳契数列(Fibonacci Sequence),又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21….. I

斐波纳契数列是典型的递归案例:

递归关系就是实体自己和自己建立关系。

Fib(0) = 1 [基本情况] Fib(1) = 1 [基本情况] 对所有 n > 1 的整数:Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义] 尽管有许多数学函数均可以递归表示,但在实际应用中,递归定义的高开销往往会让人望而却步。例如:

阶乘(1) = 1 [基本情况] 对所有 n > 1 的整数:阶乘(n) = (n * 阶乘(n-1)) [递归定义] 一种便于理解的心理模型,是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如:你怎样才能移动 100 个箱子?答案:你首先移动一个箱子,并记下它移动到的位置,然后再去解决较小的问题:你怎样才能移动 99 个箱子?最终,你的问题将变为怎样移动一个箱子,而这时你已经知道该怎么做的。

如此的定义在数学中十分常见。例如,集合论对自然数的正式定义是:1 是一个自然数,每个自然数都有一个后继,这一个后继也是自然数。

德罗斯特效应是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片,进而小图片中还有更小的一幅她手持同一物体的图片,依此类推。

又例如,我们在两面相对的镜子之间放一根正在燃烧的蜡烛,我们会从其中一面镜子里看到一根蜡烛,蜡烛后面又有一面镜子,镜子里面又有一根蜡烛……这也是递归的表现。

收藏 0个人收藏
走进科技生活方式

评论交流

泪雪默认头像 请「登录」后参与评论
  1. 加载中..

相关推荐

  • DNS hijack 域名劫持

    什么是域名劫持

    域名劫持是互联网攻击的一种方式,通过攻击域名解析服务器,或伪造域名解析服务器的方法,把目标网站域名解析到错误的IP地址从而实现用户无法访问目标网站的目的或者蓄意或恶意要求用户访问指定IP地址(网站)的目的。
  • sort 排序

    排序算法稳定性是指什么

    排序算法稳定性指假定在待排序的记录序列中,存在多个具有相同的关键字的记录,经过排序这些记录的相对次序保持不变,则是稳定的;否则为不稳定。不稳定的算法在某种条件下可以变为稳定的算法,而稳定的算法在某种条件下也可以变为不稳定的算法。
  • 什么是存储分配

    什么是存储分配

    编译程序的整个编译过程大体分成五部分:词法分析、语法分析、代码优化、存储分配和代码生成。在代码生成之前还必须先确定程序、变量以及常数在内存中存放的地址,这些统称为存储分配。
  • 动态规划是什么

    动态规划是什么

    动态规划是运筹学的一个分支,是求解决策过程最优化的数学方法。
  • 加权数据融合是什么

    加权数据融合是什么

    加权数据融合是对多源冗余信息进行加权平均,结果作为融合值,是一种直接对数据源进行操作的方法。
  • 可变参数模板是什么

    可变参数模板是什么

    可变参数模板是模板编程时,模板参数的个数可变的情形。已经支持可变参数模板的编程语言有D语言与C++。可变模板参数是C++ 11新增的最强大的特性之一,它对参数进行高度泛化,它能表示0到任意个数、任意类型的参数。