算法 递归

星期三, 8月 7, 2019 | 2分钟阅读 | 更新于 星期日, 9月 8, 2019

@

一、定义

程序调用自身的编程技巧称为递归。递归作为一种算法在程序设计语言中广泛应用。 一个方法或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

循环都可以改写成递归,递归未必能改写成循环

二、条件

什么样的问题才可以使用递归的方式求解呢?构成递归需要具备两个条件:

  1. 子问题与原始问题为同样的事情,二者的求解方法是相同的,且子问题比原始问题更易求解。
  2. 递归不能无限制地调用本身,必须有个递归出口。递归出口对应的情形相对简单,可以化简为非递归状况处理。

三、适用场景

  1. 数据的定义是按递归定义的。如Fibonacci函数。
  2. 问题解法按递归算法实现。如Hanoi问题。
  3. 数据的结构形式是按递归定义的。如二叉树、广义表等。

四、设计思路

  1. 确定递归出口
  2. 找出递归表达式

一般而言,如果一个问题可以分成n个步骤,每一个步骤是相同的方法,后一个方法依赖前面方法,形如Fn = Fn-1 + Fn-2、Fn = Fn-1 + Fn-2 + Fn-3、Fn = Fn-1 * Fn-2等关系,而F1等又是确定的值,则可以推出具体的n对应的值,就确定递归函数

© 2026 我的博客

🌱 Powered by Hugo with theme Dream.

关于这个博客

关于博客

记录软件开发过程的一些知识和技巧,提升自我

关于博主

除了才华一无所有~~ 薪尽自然凉~~ 强迫症患者~~ 热爱古风~~