1、递归简介

  • 算法思想
    • 递归就是自己调用自己，执行同样的步骤
    • 递归有基线条件和递归条件，基线条件就是退出递归的条件，避免死循环；递归条件就是自己调用自己
  • 举个栗子
    • 递归就像是拆箱子，找到里面的钥匙。你拆箱子A，A里面有箱子B 和 箱子C，此时你又去拆箱子B，B里面有箱子D，你又去拆箱子D，箱子D是个空箱子，此时通过栈保存的方法调用，回到拆箱子B结束后。此时拆箱子C….。找到了钥匙即退出
  • 优点
    • 理解简单

  • 缺点

    • 假如递归很长，需要栈来保存调用方法的信息，占用大量内存，会导致栈溢出

      2、递归转换

      2.1、递归转非递归（循环）

  • 递归的实质是使用栈来保存方法的执行状态，然后调用自己进入下个状态，函数返回的时候则回到上次保存的状态

  • 思路

    • 自己创建一个栈，栈里面保存的一个记录，包括局部变量的值和方法的执行位置
    • 首先将局部变量初始化为一开始的状态，然后进入一个循环
    • 执行代码时，遇到递归，就制作状态压栈保存，然后更新局部变量进入下一层
    • 如果一个调用结束了，就要返回上层状态。直接将栈里的记录弹出，拿来更新当前状态即可
    • 某个调用结束时如果栈为空，则所有调用都结束，退出主循环
    • 递归转循环

      2.2、递归转尾递归

  • 尾递归是指 递归的最后是调用自身，此时调用栈是常量栈