算法图解/chap03-递归.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第3章 递归\n",
    "\n",
    "这两种方法的作用相同，但在我看来，第二种方法更清晰。递归只是让解决方案更清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。\n",
    "\n",
    "我很喜欢Leigh Caldwell在Stack Overflow上说的一句话：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。([参考链接](http://stackoverflow.com/a/72694/139117))” 很多算法都使用了递归，因此理解这种概念很重要。\n",
    "\n",
    "## 3.2基线条件和递归条件\n",
    "\n",
    "由于递归函数调用自己，因此编写这样的函数时很容易出错，进而导致无限循环。例如，假设你要编写一个像下面这样倒计时的函数。\n",
    "```\n",
    "def countdown(i):\n",
    "    print i\n",
    "    countdown(i-1)\n",
    "```\n",
    "如果你运行上述代码，将发现一个问题：这个函数运行起来没完没了！\n",
    "\n",
    "编写递归函数时，必须告诉它何时停止递归。正因为如此，每个递归函数都有两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件则指的是函数不再调用自己，从而避免形成无限循环。\n",
    "\n",
    "我们来给函数 countdown 添加基线条件。\n",
    "\n",
    "现在，这个函数将像预期的那样运行，如下所示。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "9\n",
      "8\n",
      "7\n",
      "6\n",
      "5\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "def countdown(i):\n",
    "    print((i))\n",
    "    if i <= 0:\n",
    "        return\n",
    "    else:\n",
    "        countdown(i-1)\n",
    "        \n",
    "countdown(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.3栈 stack\n",
    "\n",
    "本节将介绍一个重要的编程概念——调用栈（call stack）。调用栈不仅对编程来说很重要，使用递归时也必须理解这个概念。假设你去野外烧烤，并为此创建了一个待办事项清单——一叠便条。\n",
    "\n",
    "本书之前讨论数组和链表时，也有一个待办事项清单。你可将待办事项添加到该清单的任何地方，还可删除任何一个待办事项。一叠便条要简单得多：插入的待办事项放在清单的最前面；读取待办事项时，你只读取最上面的那个，并将其删除。因此这个待办事项清单只有两种操作：压入（插入）和弹出（删除并读取）。\n",
    "\n",
    "### 3.3.1 调用栈\n",
    "\n",
    "计算机在内部使用被称为调用栈的栈。我们来看看计算机是如何使用调用栈的。下面是一个简单的函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "hello, maggie!\n",
      "how are you, maggie?\n",
      "getting ready to say bye...\n",
      "ok bye!\n"
     ]
    }
   ],
   "source": [
    "def greet(name):\n",
    "    print(\"hello, \" + name + \"!\")\n",
    "    greet2(name)\n",
    "    print(\"getting ready to say bye...\")\n",
    "    bye()\n",
    "    \n",
    "#这个函数问候用户，再调用另外两个函数。这两个函数的代码如下。\n",
    "def greet2(name):\n",
    "    print(\"how are you, \" + name + \"?\")\n",
    "def bye():\n",
    "    print(\"ok bye!\")\n",
    "             \n",
    "greet(\"maggie\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面详细介绍调用函数时发生的情况:\n",
    "\n",
    "- 1.调用 greet(\"maggie\")，计算机为grreet函数调用分配一块内存。其中的name = maggie\n",
    "- 2.打印 hello, maggie!\n",
    "- 3.调用greet2(\"maggie\")，计算机为grreet2函数调用分配一块内存，计算机使用一个栈来表示这些内存块，第二个内存块（greet2）位于第一个内存块(greet)上面。其中的name = maggie\n",
    "- 4.打印how are you, maggie? ，然后从函数调用返回。此时，栈顶的内存块（greet2）被弹出。\n",
    "- 5.现在，栈顶的内存块是函数 greet 的，这意味着你返回到了函数 greet 。当你调用函数 greet2时，函数 greet 只执行了一部分。这是本节的一个重要概念：**调用另一个函数时，当前函数暂停并处于未完成状态**。该函数的所有变量的值都还在内存中。执行完函数 greet2 后，你回到函数greet ，并从离开的地方开始接着往下执行\n",
    "- 6.首先打印 getting ready to say bye\n",
    "- 7.再调用函数 bye 。在栈顶添加了函数 bye 的内存块。然后，你打印 ok bye! ，并从这个函数返回。\n",
    "- 8.现在你又回到了函数 greet 。由于没有别的事情要做，你就从函数 greet 返回。\n",
    "\n",
    "这个栈用于存储多个函数的变量，被称为调用栈。\n",
    "\n",
    "### 3.3.2 递归调用栈\n",
    "\n",
    "递归函数也使用调用栈！来看看递归函数 factorial 的调用栈。 factorial(5) 写作5!，其定义如下：5! = 5 * 4 * 3 * 2 * 1。同理， factorial(3) 为3 * 2 * 1。下面是计算阶乘的递归函数。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def fact(x):\n",
    "    if x==1:\n",
    "        return 1\n",
    "    else:\n",
    "        return x*fact(x-1)\n",
    "    \n",
    "fact(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意，每个 fact 调用都有自己的 x 变量。在一个函数调用中不能访问另一个的 x 变量。栈在递归中扮演着重要角色。这个栈包含未完成的函数调用，每个函数调用都包含还未检查完的盒子。使用栈很方便，因为你无需自己跟踪盒子堆——栈替你这样做了。\n",
    "\n",
    "使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择。\n",
    "- 重新编写代码，转而使用循环。\n",
    "- 使用尾递归。这是一个高级递归主题，不在本书的讨论范围内。另外，并非所有的语言都支持尾递归。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (system-wide)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}