递归

普通递归

• 当函数返回到上一层级操作的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文

尾递归

• 递归调用是函数返回前的最后一个操作，这意味着函数返回上一级后，无需执行其他操作，因此系统无需保存上一层函数的上下文

不同点

• 普通递归：求和操作是在“归”的过程中执行的，每层返回后都要再执行一次求和操作
• 尾递归：求和操作是在“递”的过程中执行的，“归”的过程只需层层返回

迭代和递归的对比

实现方式

• 迭代：循环结构
• 递归：函数调用自身

时间效率

• 迭代：效率通常较高，无函数调用开销
• 递归：每次调用函数都会产生开销

内存使用

• 迭代：通常使用固定大小的内存空间
• 递归：累积函数调用可能使用大量的栈帧空间

适用问题

• 迭代：适合于简单循环任务，代码直观，可视性好
• 递归：适用于子问题分解，如树、图、分治、回溯等，代码结构简洁清晰

递归和栈之间的关系

1. 递：当函数被调用时，系统会在“调用栈”上为该函数分配新的栈帧，用于存储函数的局部变量、参数、返回地址等数据
2. 归：当函数完成执行并返回时，对应的栈帧会被从“调用栈”上移除，恢复之前函数的执行环境