单向递归

回顾上一章的内容

二阶阶乘

使用普通递归来解决

把普通递归转化成尾递归

把尾递归转化成迭代

颠倒二进制位

使用普通递归来解决

把普通递归转化成尾递归

把尾递归转化成迭代

---

参数传递

值传递

引用传递

递归三要素

• 递归的定义

• 递归的拆解

• 递归的出口

爆栈

递归调用将栈空间消耗完

---

尾递归

尾递归的特点

• 函数中所有递归形式的调用都出现在函数的末尾
• 递归调用不属于表达式的一部分

尾递归的作用

• 尾递归的调用不会在栈中去创建一个新的
• 而是覆盖当前的活动记录

为什么可以尾递归

• 在回归过程中不用做任何操作

---

支持尾递归的语言

• Kotlin
• Haskell

不支持尾递归的语言

• Java
• Python
• C++

---

不支持尾递归优化的语言如何避免爆栈

尾递归优化就是把递归改成迭代形式

---

如何改成迭代呢

模拟递归中调用下一层的参数传递过程

1. 先做完本层递归的事儿
2. 再计算出下一层递归的各个参数
3. 然后把值赋给当前层的各个参数

妙用

两两交换链表中的节点

• 递归的方式

• 迭代的方式

经典二分查找问题

• 普通写法的递归方式

• 二分查找的递归方式

快速幂

• 普通写法的递归方式

• 快速幂的递归方式

递归时间复杂度的分析

时间复杂度= 函数参数的可能组合*每层递归的处理时间

函数参数的可能组合 ：O(n)

每层递归的时间：O(1)