{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d4a53758",
   "metadata": {},
   "source": [
    "# 函数进阶\n",
    "\n",
    "## 函数的参数传递"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5e628c6f",
   "metadata": {},
   "source": [
    "Python的函数采用了引用传递的方法，即传递参数时，并不复制一份参数的内容，而是将参数的引用传递给函数。\n",
    "\n",
    "例如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "003fa7c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    return id(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "fef96338",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 1.2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "bedf2afb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4485901776"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "id(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "a10c5f49",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4485901776"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f66b0b35",
   "metadata": {},
   "source": [
    "函数`f(a)`的返回值与a的内存地址是一致的。这表示，当函数`f()`被调用时，Python并没有将a的值复制一份传给参数x，而是让参数x与a共享了同一块内存。所以a和x是同一个对象。\n",
    "\n",
    "对于列表有类似的结论："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "40de4e9c",
   "metadata": {},
   "outputs": [],
   "source": [
    "b = [1, 2, 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "209b58ca",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4486278400"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "3ba2ebff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4486278400"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "id(b)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "255f72f0",
   "metadata": {},
   "source": [
    "共享同一个对象的机制意味着，可以在函数中修改传入参数的值。例如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2fc37814",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mod_f(x):\n",
    "    x[0] = 999\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "426c51d7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "1b77b973",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[999, 2, 3]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mod_f(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "4f014365",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[999, 2, 3]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cd196d65",
   "metadata": {},
   "source": [
    "不过，如果在函数中给参数x赋了一个新值，如另一个列表，根据赋值机制，虽然x指向一个新的内存位置，但原来的变量不会改变："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "68dce8b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def no_mod_f(x):\n",
    "    x = [4, 5, 6]\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "7b474ccc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 5, 6]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "no_mod_f(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "b3bed828",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[999, 2, 3]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e16cf62a",
   "metadata": {},
   "source": [
    "## 默认参数的传递"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "587198fd",
   "metadata": {},
   "source": [
    "有默认参数的情况下，Python会在函数定义时，预先为默认参数分配内存，以避免每次生成一个额外的默认参数。这样做能够节约一定的空间，不过也可能会得到一些与直觉不符的结果。例如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "133b2be2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x = []):\n",
    "    x.append(1)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc5dbb86",
   "metadata": {},
   "source": [
    "理论上说，调用 `f()` 时返回的是 `[1]`， 但事实上："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "ec4cbacd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "ef5c79b5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "ca57f94d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 1]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "147f8237",
   "metadata": {},
   "source": [
    "随着函数的调用，默认参数会被一直改变。这并不是Python的bug，且这种特性可以用于缓存。如果不想要这样的特性，可以这样定义函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "23a441a7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x = None):\n",
    "    if not x:\n",
    "        x = []    \n",
    "    x.append(1)\n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "bbfaae61",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "5499605d",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60aa85c8",
   "metadata": {},
   "source": [
    "## 高阶函数"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "544e2088",
   "metadata": {},
   "source": [
    "以函数作为参数，或者返回一个函数的函数都是高阶函数。在Python中，函数也是一种基本类型的对象，例如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "04188365",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<function max>"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "2a9115d0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "builtin_function_or_method"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(max)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05b2407d",
   "metadata": {},
   "source": [
    "对象性意味着可以对函数进行以下操作：\n",
    "- 将函数作为参数传给另一个函数。\n",
    "- 将函数名赋值给另一个变量。\n",
    "- 将函数作为另一个函数的返回值。\n",
    "\n",
    "例如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "97429c11",
   "metadata": {},
   "outputs": [],
   "source": [
    "def square(x):\n",
    "    \"\"\"Square of x.\"\"\"\n",
    "    return x*x\n",
    "\n",
    "def cube(x):\n",
    "    \"\"\"Cube of x.\"\"\"\n",
    "    return x*x*x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fdec6e5",
   "metadata": {},
   "source": [
    "可以将它们作为字典的值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "71a6e5c6",
   "metadata": {},
   "outputs": [],
   "source": [
    "funcs = {\n",
    "    'square': square,\n",
    "    'cube': cube,\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44fd6211",
   "metadata": {},
   "source": [
    "调用这些函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "52beca84",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "funcs['square'](3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d602c33a",
   "metadata": {},
   "source": [
    "常见的高阶内置函数有 `map()` 和 `filter()`。\n",
    "```python\n",
    "map(f, sq)\n",
    "```\n",
    "将函数f作用在序列sq的每个元素上，得到结果组成的新序列。例如"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "37aadbcc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<map at 0x10b6b0130>"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "map(square, range(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57b1ab3f",
   "metadata": {},
   "source": [
    "返回的结果是一个map迭代器，可以将其转换为列表："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "dfb14a37",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 9, 16]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(square, range(5)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b4c448d",
   "metadata": {},
   "source": [
    "```python\n",
    "filter(f, sq)\n",
    "```\n",
    "将函数f作用在序列sq的每个元素上，保留所有结果为`True`的元素。例如："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "f0025e81",
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_even(x):\n",
    "    return x % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "007342c0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<filter at 0x10b6b05b0>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "filter(is_even, range(5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "6ab0af5b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 2, 4]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(filter(is_even, range(5)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5ef5539",
   "metadata": {},
   "source": [
    "函数的返回值也可以是个函数。例如，定义一个返回函数的函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "eca0808b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def power_func(num):\n",
    "    def func(x):\n",
    "        return x ** num\n",
    "    return func"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c9cee080",
   "metadata": {},
   "source": [
    "平方和立方函数可以使用该函数定义出来："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "372fb5ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "square2 = power_func(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "cebe177e",
   "metadata": {},
   "outputs": [],
   "source": [
    "cube2 = power_func(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "405b8974",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(square2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "7d62ee4c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square2(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "eb9af915",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "27"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cube2(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b1a7f3ab",
   "metadata": {},
   "source": [
    "## Lambda表达式\n",
    "\n",
    "Python提供了Lambda表达式，简化函数的定义，来定义一些匿名函数。\n",
    "\n",
    "```python\n",
    "lambda <variables>: <expression>\n",
    "```\n",
    "\n",
    "Lambda表达式返回的是一个函数对象，接受`<variables>`作为参数，返回`<expression>`："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "f68cc2d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "square3 = lambda x: x ** 2\n",
    "cube3 = lambda x: x ** 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "0bc83b6e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "function"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(square3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "e561c2d9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "square3(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "7bfd0448",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "27"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cube3(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3e566e61",
   "metadata": {},
   "source": [
    "## 关键字global\n",
    "\n",
    "在Python中，函数可以直接使用外部已定义好的变量值："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "7be8cb1d",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 15\n",
    "\n",
    "def print_x():\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "0c885e94",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "print_x()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a234f1c7",
   "metadata": {},
   "source": [
    "如果想在函数中直接改x的值，需要加上关键字`global`："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "5d3e45b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 15\n",
    "\n",
    "def print_newx():\n",
    "    global x\n",
    "    x = 18\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "97a2c48f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18\n"
     ]
    }
   ],
   "source": [
    "print_newx()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "b6fe7566",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a236dc2a",
   "metadata": {},
   "source": [
    "如果不加，x的值不会改变："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "12449e81",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 15\n",
    "\n",
    "def print_newx():\n",
    "    x = 18\n",
    "    print(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "bd43caef",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18\n"
     ]
    }
   ],
   "source": [
    "print_newx()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "d5927808",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "106a7a1b",
   "metadata": {},
   "source": [
    "## 递归\n",
    "\n",
    "递归是指函数在执行的过程中调用了本身，一般用于分治法。例如，阶乘函数："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "b170fc70",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fact(n):\n",
    "    return 1 if n == 0 else n * fact(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "a9c58005",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "720"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fact(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dadb8173",
   "metadata": {},
   "source": [
    "递归可以更快地实现代码，不过在效率上可能会有一定的损失。例如，斐波那契数列："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "eb80c5e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib1(n):\n",
    "    \"\"\"Fib with recursion.\"\"\"\n",
    "    return 1 if n in (0, 1) else fib1(n-1) + fib1(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "32a8c66e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(fib1, range(10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c88745c",
   "metadata": {},
   "source": [
    "非递归的方式的实现："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "63bab4c4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib2(n):\n",
    "    \"\"\"Fib without recursion.\"\"\"\n",
    "    a, b = 1, 1\n",
    "    for i in range(1, n+1):\n",
    "        a, b = b, a+b\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "22254370",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(fib2, range(10)))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71b560a1",
   "metadata": {},
   "source": [
    "对这两个函数的运行时间进行比较："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "d5235418",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.98 ms ± 30.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 100 fib1(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "c442f901",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.5 µs ± 20.1 ns per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 100 fib2(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53d2df9f",
   "metadata": {},
   "source": [
    "可以看到，两者的效率有很大的差别，非递归版本比递归版本要快很多，原因是递归版本中存在大量的重复计算。\n",
    "\n",
    "为了减少递归中的重复，可以利用默认参数实现缓存机制："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "a0aeb950",
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib3(n, cache={0: 1, 1: 1}):\n",
    "    \"\"\"Fib with recursion and caching.\"\"\"\n",
    "    try:\n",
    "        return cache[n]\n",
    "    except KeyError:\n",
    "        cache[n] = fib3(n-1) + fib3(n-2)\n",
    "        return cache[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "e6f6e4f6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(map(fib3, range(10)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "142964a0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "158 ns ± 49.9 ns per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n 100 fib3(20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "380e5024",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}