老师问您一个看起来很弱智的问题哈，但我就是不明白

Question

这个是递归终止的条件，如果递归下去某个时刻没有左子树或者没有右子树的时候，那不就在这个递归中节点为空直接返回false了嘛，那么返回false会对它的上层递归有什么影响嘛，不会导致整个程序都退出把

Answer 1

liuyubobobo 2021-07-14 17:50:00

返回到上层递归函数，上层递归函数会基于这个返回结果进行相应的逻辑呀。

在 if(contains(node->left, key) || contains(node->right, key)) 中，对调用的函数返回的结果进行了使用，而不是整个程序退出。

递归函数调用和普通函数调用没有区别。只不过调用的函数是自己而已。一个函数执行完毕，返回到上层调用的函数继续执行（而不会整个程序退出。）

我建议你创建一个小的测试用例，用单步跟踪的方式，仔细理解一下这个递归调用的过程到底是怎么执行的。更进一步，我建议你对于经典算法中的递归算法，比如归并排序，或者是链表反转，都重新进行一下理解。如果有需要，可以参考这个课程，其中对递归的微观执行过程有详细解读：https://class.imooc.com/sale/datastructure

继续加油！：）

• 提问者 不考过程序员不改名字 #1

  谢谢老师这么耐心的回答，一直都不太理解递归，虽然本科和考研的时候都学过，但是对递归很排斥，总感觉脑子转不过来一样，哭了

• liuyubobobo 回复 提问者 不考过程序员不改名字 #2

  踏下心来搞明白一点儿都不难。相信我。加油！：）

• 提问者 不考过程序员不改名字 回复 liuyubobobo #3

  好嘞，谢谢您！