递归和栈

layout: post
title: 数据结构与算法—递归和栈
date: 2019-9-28
tag: 数据结构与算法

递归

递归有两个条件：基线条件（递归停止的条件）、递归条件（递归继续的条件）

栈

先入后出的数据结构，只有两种操作：压入（插入）和弹出（删除并读取）

以做菜为例：在开始做菜时，你需要确定做菜的循序或者步骤，此时就是压入栈的过程，在做菜的过程中，需要一步一步的来，做完一步就撕掉该步骤，这个过程就是弹出栈的过程

递归使用到了调用栈的概念

以计算 为例看一下递归的过程

使用栈的代价：

使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择。

• 重新编写代码，转而使用循环。
• 使用尾递归。这是一个高级递归主题。另外，并非所有的语言都支持尾递归。

小结

• 递归指的是调用自己的函数。
• 每个递归函数都有两个条件：基线条件和递归条件。
• 栈有两种操作：压入和弹出。
• 所有函数调用都进入调用栈。
• 调用栈可能很长，这将占用大量的内存。
• 如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。