什么是递归算法?

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

缺点

递归是不断调用自身的过程,由于没执行一次函数,都会开辟一块新的内存空间,而递归不断调用自身时,会导致系统的性能下降,对服务器的要求较高,其实就是一种以空间换时间的方法。

应用场景

 什么样的问题才可以使用递归的方式求解呢?构成递归需要具备两个条件:
  (1)子问题与原始问题为同样的事情,二者的求解方法是相同的,且子问题比原始问题更易求解。
  (2)递归不能无限制地调用本身,必须有个递归出口。递归出口对应的情形相对简单,可以化简为非递归状况处理。

实例

  1. 发波那契数列
  2. 阶乘
  3. 树的遍历
  4. 遍历文件夹
  5. 汉诺塔
  6. 逆序打印字符串
  7. 求二叉树的深度