{ "cells": [ { "cell_type": "markdown", "id": "d98bd694", "metadata": {}, "source": [ "# Recursion\n", "\n", "It is legal for a function to call itself.\n", "It may not be obvious why that is a good thing, but it turns out to be one of the most magical things a program can do.\n", "Here's an example." ] }, { "cell_type": "code", "execution_count": null, "id": "d0624a7a", "metadata": {}, "outputs": [], "source": [ "import sys\n", "from pathlib import Path\n", "\n", "# Find project root by looking for _config.yml\n", "current = Path.cwd()\n", "for parent in [current, *current.parents]:\n", " if (parent / '_config.yml').exists():\n", " project_root = parent\n", " break\n", "else:\n", " project_root = Path.cwd().parent.parent\n", "\n", "# Add project root to path\n", "sys.path.insert(0, str(project_root))\n", "\n", "# Import shared teaching helpers and cell magics\n", "from shared import thinkpython, diagram, jupyturtle, structshape\n", "from shared.download import download\n" ] }, { "cell_type": "code", "execution_count": null, "id": "9e75d74e", "metadata": {}, "outputs": [], "source": [ "def countdown(n):\n", " if n <= 0:\n", " print('Blastoff!')\n", " else:\n", " print(n)\n", " countdown(n-1)" ] }, { "cell_type": "markdown", "id": "36e3e1ad", "metadata": {}, "source": [ "If `n` is 0 or negative, `countdown` outputs the word, \"Blastoff!\" Otherwise, it\n", "outputs `n` and then calls itself, passing `n-1` as an argument.\n", "\n", "Here's what happens when we call this function with the argument `3`." ] }, { "cell_type": "code", "execution_count": null, "id": "169b84c3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n", "2\n", "1\n", "Blastoff!\n" ] } ], "source": [ "countdown(3)" ] }, { "cell_type": "markdown", "id": "5e30953e", "metadata": {}, "source": [ "The execution of `countdown` begins with `n=3`, and since `n` is greater\n", "than `0`, it displays `3`, and then calls itself\\...\n", "\n", "> The execution of `countdown` begins with `n=2`, and since `n` is\n", "> greater than `0`, it displays `2`, and then calls itself\\...\n", ">\n", "> > The execution of `countdown` begins with `n=1`, and since `n` is\n", "> > greater than `0`, it displays `1`, and then calls itself\\...\n", "> >\n", "> > > The execution of `countdown` begins with `n=0`, and since `n` is\n", "> > > not greater than `0`, it displays \"Blastoff!\" and returns.\n", "> >\n", "> > The `countdown` that got `n=1` returns.\n", ">\n", "> The `countdown` that got `n=2` returns.\n", "\n", "The `countdown` that got `n=3` returns." ] }, { "cell_type": "markdown", "id": "497207b1", "metadata": {}, "source": [ "**A function that calls itself** is **recursive**.\n", "As another example, we can write a function that prints a string `n` times." ] }, { "cell_type": "code", "execution_count": null, "id": "9f78713d", "metadata": {}, "outputs": [], "source": [ "def print_n_times(string, n):\n", " if n > 0:\n", " print(string)\n", " print_n_times(string, n-1)" ] }, { "cell_type": "markdown", "id": "7f17600c", "metadata": {}, "source": [ "If `n` is positive, `print_n_times` displays the value of `string` and then calls itself, passing along `string` and `n-1` as arguments.\n", "\n", "If `n` is `0` or negative, the condition is false and `print_n_times` does nothing.\n", "\n", "Here's how it works." ] }, { "cell_type": "code", "execution_count": null, "id": "f19d4f07", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Spam \n", "Spam \n", "Spam \n", "Spam \n" ] } ], "source": [ "print_n_times('Spam ', 4)" ] }, { "cell_type": "markdown", "id": "d8dbe1e9", "metadata": {}, "source": [ "For simple examples like this, it is probably easier to use a `for`\n", "loop. But we will see examples later that are hard to write with a `for`\n", "loop and easy to write with recursion, so it is good to start early." ] }, { "cell_type": "markdown", "id": "7f59321f", "metadata": {}, "source": [ "## Stack diagrams for recursive functions\n", "\n", "Here's a stack diagram that shows the frames created when we called `countdown` with `n = 3`." ] }, { "cell_type": "code", "execution_count": null, "id": "c266301c", "metadata": {}, "outputs": [], "source": [ "from shared.diagram import make_frame, Stack\n", "\n", "frames = []\n", "for n in [3,2,1,0]:\n", " d = dict(n=n)\n", " frame = make_frame(d, name='countdown', dy=-0.3, loc='left')\n", " frames.append(frame)\n", "\n", "stack = Stack(frames, dy=-0.5)" ] }, { "cell_type": "code", "execution_count": null, "id": "23dcdb53", "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAMIAAADgCAYAAABRhbkMAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjcsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvTLEjVAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAExRJREFUeJzt3X9IXfX/B/CXP8ifzV85bUo0BBV100la/kz8TdNm02k5CgOV+kMzhpMCN5ng/hFnqYUmn81hDmMqssYMHcqWij9WuoHOnHGRlDnLZXnNX9Mvr9f53ov9cHOFXrf7fMDlnnPPueec+z7v1/v1esuVa7C2trZGAHrOUNcXALATIBAAEAgACmQEAAQCgAIZAQCBAKBARgBAIAAokBEAEAgACmQEAAQCgAIZAQCBAKBARgBAIAAokBEAEAgACmQEAAQCgML4/59Bx37//XddX8IT4dlnn92S46I0AkAgACiQEQAQCAAKZAQABAKAAhkBAIEAoEBGAHiaA6G0tJTu3r274fby8nJKS0vb1msCxaFDhyggIICCgoIoJiaGBgcHSdeMn+ZACAsLI0dHR11fCvxFTU0NWVtby/KlS5fo/fffp66uLtKrjNDd3U3BwcHk7e1N+/fvp+bmZurv76fAwEBZ9/f3p87OTtlXpVJpG4zNzc2RgYGBdp2Xi4qK5D179+6ls2fPyuunTp2iyclJSklJIR8fHxoYGJDv8vC6m5ubnP/WrVva4zx48IByc3PJy8tLHllZWbS0tERqtZpsbW1peXlZ9uPzpKamyvL4+Di5uLjIckFBgRw7Pj6ePDw8KDw8nGZmZrasDXft2kXFxcUS6Pv27aPa2lrSJZVKRXV1dTQ0NESrq6uP3H/9Pf3tt9/+dE/1IiNw50hISKCLFy9SSEiINNrPP/9ML730En3xxReSJr/99ltKTEykO3fubOqYJiYm1NvbS7dv3yY/Pz96++236cSJE/S///2P6uvrJRAYd3Tel/fjxn/llVfo5Zdflm1VVVXU19dHN27cICMjI3r99dfpzJkzlJeXJ4HBwcsdjoOD9+Nf22ptbaWIiAjtdfT09Mj77ezs6M0336TKykr66KOPtqgllc/d0dFBP/zwgwQEn9PYWDcJ3t7eniwsLKilpUXagdvV3d2dDA03HmczMzPp+vXrssz9Qde2teW4Q/GIzEHAuKGmpqbkmYOA8Wjt4OAgo7izs/Mjj3n06FF55obnjsDzgn9639WrV6Vz8+hjZWUlI/vY2Jhsa2trk/kCdy6WkZFBFRUVEgiRkZGyfXp6mqKjo2l4eFiyCb/GQa0RGxsrQcC4/l2fcbZCcnKyPLu6usrn5nZ0cnL60z48QHBm3C5OTk50//59CQhu7yNHjmxYmvLgw7788ksZuBoaGkiXduRkWZMq+QZz2aKxsLDwt31NTU21yzyar6ysPNY5HrVNEwj84GV+cDZob2+XEui/Xse/pQlaxgPJVp9vq/BAxpnhl19+Ib3JCDwPGB0dlQ+uKY149Odn7lxRUVEyaeJRnUsa7lxchnDtybX3+fPnH6uOnp2d1a5zB+Y5RGhoqMwXLly4IKWUZhsfm7MEd6rq6moZ/TXzgpGREbp37x6VlJTIqHfw4EEZ6bgk2Mn42reDWq2W+zcxMUE2NjbSxhuVRr/++iv98ccf9Pzzz8v6119/LfMwfuhNIHAjNTU10bFjx6QzckMVFhZSY2MjZWdny+vc+blmtLS0lPeUlZVRXFyclB1JSUmbPhcfj0scc3NzOnfuHOXn51N6errcIO7AXIItLi5q61Uuk3x9fWWda+6cnBxtVuI/8/FE3czMjDw9PWXyvH5+oO+mp6dpfn5eysNHzQ14fvbOO+9Iduf9nnvuOfrqq690PmE2wO8s7wz4D7XNwX+oAejbZBlguyEQABAIAApkBAAEAoACGQEAgQCgQEYAQCAAKJARAPBdIwAFMgIAAgFAgYwAgEAAUCAjACAQABTICAAIBAAFMgIAAgFAgYwAgEAAUCAjACAQABTICAAIBAAFMgIAAgFAgYwA8DT/vOyTBr+PsDn4fQSALYTSCACBAKBARgBAIAAokBEAEAgACmQEAAQCwFOeEUpLS+nu3bsbbi8vL6e0tLRtvSYgWlhYoLfeeosOHDhAgYGBdOjQIRobG9N50+htIIDupKWl0XfffUddXV302muvUVZWlv4FQnd3NwUHB5O3tzft37+fmpubqb+/X0YHXvf396fOzk7ZV6VSkbW1tfa9c3NzZGBgoF3n5aKiInnP3r176ezZs/L6qVOnaHJyklJSUsjHx4cGBgbkuzy87ubmJue/deuW9jgPHjyg3Nxc8vLykgffmKWlJVKr1WRra0vLy8uyH58nNTVVlsfHx8nFxUWWCwoK5Njx8fHk4eFB4eHhNDMzs2VtuGvXLiouLqawsDDat28f1dbWki6pVCqqq6ujoaEhWl1dfei+pqamFBMTo72Pfn5+0pZ6FQjcORISEuj06dM0ODgoHTQgIIAOHz5MJ0+epJs3b1JJSQklJiZKp98MExMT6u3tpStXrlB2djatrKzQiRMnaM+ePVRfXy/n4GDg4OB9b9++TZcvX6Zr165pj1FVVUV9fX1048YN2Z9T9ZkzZ8jCwkICg4P3/v37Ehy839raGrW2tlJERIT2GD09PXTu3DnpDLt376bKysotacP1n7ujo4MaGhro+PHj8rl1xd7eXtqqpaWFampqNhUQGp9//rlkBb369il3KB6RQ0JCZN3Q0JCmpqbkmUcJxqO1g4ODdEhnZ+dHHvPo0aPy7O7uTsbGxlIO/dP7rl69Kp2bRyIrKysZ2TW1aVtbm6Rr7lwsIyODKioqKC8vjyIjI2X79PQ0RUdH0/DwsGQTfo2DWiM2Npbs7OxkmYN7fcbZCsnJyfLs6uoqn5vb0cnJ6U/78ADBmXG7ODk5yYDBAcHtfeTIEXJ0dNxwf85qP/74I126dIl0bUfOETRpk28wly3rJ1r/lGo1jIyMNj0yri+xHrZNEwj84GV+cDZob2+XEui/Xse/pQlaxgOJLjPCv/Hpp59KAHBGMzc3J73KCDwPGB0dpevXr0tW4PTJoz8/c+eKioqSCRSP6lzOcOfiMoRTLdfe58+ff6w6enZ2VrvOHZjnEKGhoTJfuHDhgtSnmm18bM4S3Kmqq6tl9NfMC0ZGRujevXtStvGod/DgQRnpuCTYyfjat4NarZb7NzExQTY2NtLGnKG5LTf6i93Fixdlfrh+Dqg3gcCN1NTURMeOHZPOyA1VWFhIjY2NUt/z69z5uZEsLS3lPWVlZRQXFydlR1JS0qbPxcfjEodHG67d8/PzKT09XW4Qd2AuwRYXF2XfzMxMKZN8fX1lnSehOTk52qwUFBQkcxYzMzPy9PSUyfP6+YG+m56epvn5eSkPHxYAjIPl448/phdffFHuK3vmmWckw+qSwRoPuaBz+A+1zcF/qAHo22QZYLshEAAQCAAKZAQABAKAAhkBAIEAoEBGAEAgACiQEQDwXSMABTICAAIBQIGMAIBAAFAgIwAgEAAUyAgACAQABTICAAIBQIGMAIBAAFAgIwAgEAAUyAgACAQABTICAAIBQIGMALDdPxQCG8PvI2wOfh8BYAuhNAJAIAAokBEAEAgACmQEAAQCgAIZAQCBAPCUZ4TS0lK6e/fuhtvLy8spLS1tW68JiHJzc8nLy4t27dpFN2/e3DFNoreBALqRkJBA33zzDb3wwgs76hZseyB0d3dTcHAweXt70/79+6m5uZn6+/spMDBQ1v39/amzs1P2ValUZG1trX3v3NwcGRgYaNd5uaioSN6zd+9eOnv2rLx+6tQpmpycpJSUFPLx8aGBgQH5Lg+vu7m5yflv3bqlPc6DBw+0IxU/srKyaGlpidRqNdna2tLy8rLsx+dJTU2V5fHxcXJxcZHlgoICOXZ8fDx5eHhQeHg4zczMbFkb8mhaXFxMYWFhtG/fPqqtrSVdUqlUVFdXR0NDQ7S6uvrQfYOCgsjJyYl2mm0NBO4cPCKcPn2aBgcHpYMGBATQ4cOH6eTJk5IqS0pKKDExUTr9ZpiYmFBvby9duXKFsrOzaWVlhU6cOEF79uyh+vp6OQcHAwcH73v79m26fPkyXbt2TXuMqqoq6uvroxs3bsj+Y2NjdObMGbKwsJDA4OC9f/++BAfvt7a2Rq2trRQREaE9Rk9PD507d046w+7du6mysnJL2nD95+7o6KCGhgY6fvy4fG5dsbe3l7ZqaWmhmpqaTQWEXn/7lDsUj8ghISGybmhoSFNTU/IcExMjr/Fo7eDgIB3S2dn5kcc8evSoPLu7u5OxsbGUQ//0vqtXr0rn5ixiZWUlIzt3eNbW1ibzBe5cLCMjgyoqKigvL48iIyNl+/T0NEVHR9Pw8LBkE36Ng1ojNjaW7OzsZJmDe33G2QrJycny7OrqKp+b2/GvIy0PEJwZt4uTk5MMGBwQ3N5HjhwhR0dHehLsyDmCpvzhG8xli8bCwsLf9jU1NdUuGxkZbXpkXF9iPWybJhD4wcv84GzQ3t4uJdB/vY5/SxO0jAcSXWaEp8G2ZgSeB4yOjtL169clK3D65NGfn7lzRUVFUVdXl4zqXM5w5+IyhFMt197nz59/rDp6dnZWu84dmOcQoaGhMl+4cOEC+fn5abfxsTlLcKeqrq6W0V8zLxgZGaF79+5J2caj3sGDB2Wk45JgJ+Nr3w5qtVru38TEBNnY2Egbc4bmtnxSbGsgcCM1NTXRsWPHpDNyQxUWFlJjY6PU9/w6d/6LFy+SpaWlvKesrIzi4uKk7EhKStr0ufh4XOKYm5tL7Z6fn0/p6elyg7gDcwm2uLgo+2ZmZkqZ5OvrK+s8Cc3JydFmJZ7g8ZzFzMyMPD09ZfK8fn6g76anp2l+fl7Kw0cFwAcffCB/NeJS7o033pD7zPNFXTNY4yEXdA7/obY5+A81gC305BRxAFsIgQCAQABQICMAIBAAFMgIAAgEAAUyAgACAUCBjACA7xoBKJARABAIAApkBAAEAoACGQEAgQCgQEYAQCAAKJARABAIAApkBAAEAoACGQEAgQCgQEYAQCAAKJARABAIAApkBIDt/qEQ2Bh+H2Fz8PsIAFsIpREAAgFAgYwAgEAAUCAjACAQABTICAAIBICnPCOUlpbS3bt3N9xeXl5OaWlp23pNoLhz5w5FRkbSgQMH6NVXX6Xh4WHSNb0NBNCdnJwcevfdd+n777+nDz/8kN577z39C4Tu7m4KDg4mb29v2r9/PzU3N1N/fz8FBgbKur+/P3V2dsq+KpWKrK2tte+dm5sjAwMD7TovFxUVyXv27t1LZ8+elddPnTpFk5OTlJKSQj4+PjQwMCDf5eF1Nzc3Of+tW7e0x3nw4AHl5uaSl5eXPLKysmhpaYnUajXZ2trS8vKy7MfnSU1NleXx8XFycXGR5YKCAjl2fHw8eXh4UHh4OM3MzGxZG+7atYuKi4spLCyM9u3bR7W1taRLKpWK6urqaGhoiFZXVx+67/T0tAQAtxc7dOgQTUxM0NjYGOlNIHDnSEhIoNOnT9Pg4KB00ICAADp8+DCdPHmSbt68SSUlJZSYmCidfjNMTEyot7eXrly5QtnZ2bSyskInTpygPXv2UH19vZyDg4GDg/e9ffs2Xb58ma5du6Y9RlVVFfX19dGNGzdkf74pZ86cIQsLCwkMDt779+9LcPB+a2tr1NraShEREdpj9PT00Llz56Qz7N69myorK7ekDdd/7o6ODmpoaKDjx4/L59YVe3t7aauWlhaqqal5aED89NNP5ODgQMbGxtrBzNnZWV7Xm2+fcofiETkkJETWDQ0NaWpqSp5jYmLkNR6tuaG4Q3IDPcrRo0fl2d3dXRqXy6F/et/Vq1elc3PDW1lZyciuGYXa2tpkvsCdi2VkZFBFRQXl5eVJLcvbeSSLjo6WepazCb/GQa0RGxtLdnZ2sszBvT7jbIXk5GR5dnV1lc/N7ejk5PSnfXiA4My4XZycnGTA4IDg9j5y5Ag5OjrSk2BHzhE05Q/fYC5bNBYWFv62r6mpqXbZyMho0yPj+hLrYds0gcAPXuYHZ4P29nYpgf7rdfxbmqBlPJDoMiM8Dh6kOGg118vZlbPBZga9pyYj8DxgdHSUrl+/LlmB0yeP/vzMnSsqKoq6urpkVOdyhjsXNxSnWq69z58//1h19OzsrHadOzDPIUJDQ2W+cOHCBfLz89Nu42NzluBOVV1dLaO/Zl4wMjJC9+7dk7KNR72DBw/KSMclwU7G174d1Gq13D+u9W1sbKSNOUNzW/4VtxnPD7ls5WzOc0RuU818Sy8CgRupqamJjh07Jp2RG6qwsJAaGxulvufXufNfvHiRLC0t5T1lZWUUFxcnZUdSUtKmz8XH4xLH3Nxcavf8/HxKT0+XG8Q3g0uwxcVF2TczM1PKJF9fX1nnSSj/ZUOTlYKCgmTOYmZmRp6enjJ5Xj8/0HfT09M0Pz8v5eFGAbDeJ598In8p4gk/D1ifffYZ6ZrBGg+5oHP4D7XNwX+oAejbZBlguyEQABAIAApkBAAEAoACGQEAgQCgQEYAQCAAKJARAPBdIwAFMgIAAgFAgYwAgEAAUCAjACAQABTICAAIBAAFMgIAAgFAgYwAgEAAUCAjACAQABTICAAIBAAFMgIAAgFAgYwAgEAAUCAjAAHR/wHojkg9JeT3UQAAAABJRU5ErkJggg==", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from shared.diagram import diagram, adjust\n", "\n", "\n", "width, height, x, y = [1.74, 2.04, 1.05, 1.77]\n", "ax = diagram(width, height)\n", "bbox = stack.draw(ax, x, y)\n", "# adjust(x, y, bbox)" ] }, { "cell_type": "markdown", "id": "37979942", "metadata": {}, "source": [ "The four `countdown` frames have different values for the parameter `n`.\n", "The bottom of the stack, where `n=0`, is called the **base case**.\n", "It does not make a recursive call, so there are no more frames." ] }, { "cell_type": "code", "execution_count": null, "id": "8ccdc572", "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXUAAACuCAYAAADJc52QAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjcsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvTLEjVAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAF0pJREFUeJzt3QlsTekbBvC3NDS1kxpiCf6IXe1LMfYtokaoLaEVQSSjhAnGTijRoKKG2BNLWxPBILXFFsQSzARjX6cSKvZlrP3neZNz03Z6Wm3vcu7X55dIl3vvuWd9vvd7z+1MQFpaWpoQEZERCvl6BYiIyH0Y6kREBmGoExEZhKFORGQQhjoRkUEY6kREBmGoExEZhKFORGQQhjoRkUEY6kREBmGoExEZhKFORGQQhjoRkUEY6kREBmGoExEZhKFORGQQhjoRkUEY6kREBmGoExEZhKFORGQQhjoRkUECfb0C5B1v3rzhriZykBIlSnhkuazUiYgMwlAnIjIIQ52IyCAMdSIigzDUiYgMwlAnIjIIQ52IyCAMdSIigzDUiYgM4vehvmfPHpk4cWKOz3v58qUsWrTII+tw+fJlSUhIyPC70NBQY/6K88GDB7J+/fpsn3Px4kWJjIyUgqBBgwb6tXfv3rJ3794Mj40dO1bi4+NzXEb65y1cuFCmTJmS42vwvK1bt+Z5vcm9/v33XxkyZIg0adJE2rZtK+Hh4XLnzh3xNb8O9S9fvkjfvn1l2bJljgt1/M5TfwbsbQ8fPpQNGzZkexyaNm0qmzZt8up6EflaZGSkFjSnT5/WQf7nn3/29So5M9QDAgJkxowZOgLWrl07Q3WCx2bPni0tWrSQadOmaZD069dPHzt27JhWUePGjZPGjRtL/fr15cKFC67KCJUzKujmzZvbvvf9+/eldOnS+h7NmjWTmjVryv79+22f//TpU5k1a5YcPXpUl433sdYTAwlUq1ZNtwejeZUqVWT16tWyceNGadOmjT6WfkA4f/68dO7cWdcR279jxw79fWpqqnTv3l0aNmwojRo1kqioKPGEDx8+6ImK/WtVHxMmTJBbt25JWFiYDBo0SJ+H/Yzt7tixo4wZM0ZOnjypj1uVPbZzwYIF0qFDBz0WBw4ccL3Hvn37dPuwfCwD+wCv8SUc923btsm1a9fk27dv2T63XLly37XMz58/63mEfYR9M2LECHnx4kW2r/n69aueK61atdJ/kydPlk+fPuljxYsXl6CgIDFJyZIlJTY2VvcRzu0tW7b4zXkQFBQkPXr00GsdcM2gAPI1x/4HvbCjLl26JHfv3tUAwEWBix8KFy6s4QeZq8Pr169rq2DVqlUantOnT9dAwfcIXVTQOXn16pUG59y5cyU5OVmio6N1FM5K+fLlZd68ebJr1y79Z+fdu3c6mt++fVtPXqzXmTNndDuw7MGDB+sgMHr0aB1EKlasKM+ePdMKGOGXlJQk1atXl4MHD+rynj9/Lp5w+PBhXQ9r/+J9rl69KlOnTpVTp05leC4ew2CGY4VQz7wPEfzYzkOHDml7ARcABicMuvgdBmxcxJ7altwICQmRYsWK6fE+e/asBmqdOnWkUKH/1j3Hjx93fY/CIiYmxvXzo0eP9PhCXFycBAcHa7EBixcvlvnz58vSpUtt1wODPSq/EydO6HmOQRRtGrQYx48fLyYqWrSo7qObN29quONaCAwMdPx5kNlvv/1mmxPe5NhQHzVqlH6tUaOGVns4ya1QHzlypO3rUFnjQAAqYVQBuYURuH///q5luKNPZlW4WD8sf8CAAfozBiyEGoIUoY9BrFevXhlee+PGDWndurW2mSZNmqT7o2fPnuIJCGJcXAiRdu3a6ezAzrBhw1xVSmbYRrTGoGXLlnLv3j39HoMF3gOBDkOHDtWZgJ1z587J48ePxVsqVaqk1TQu6iNHjsjAgQOlQoUKts9HoPfp08f1szVTA/TbX79+rfd9ABV31apVs31/hBv2K4IOMGtau3btd9038lcRERH6FecEwvzJkyd6HPzpPIiNjdVr948//hBfc2yoZ5Y+PDANtZN+eopKB/3e3MIFZb0floEpcX5lXi/rZ7wP/mE909LStGWEcM8KZhmopHfu3CkzZ87UmQyW5U6YDeACwiCKKhztEbt7EahovLkP/Q2O55IlS6RLly55XobdoGkSawADVMR5uWZ9acWKFRrmu3fv1pmZrzk21DENnTNnjva4MLVfvnx5vnt36BejWipSpIjb1tNaNtoN+YU2CypaBHfXrl1dQV6vXj1JSUnR6gFVDap0tH3evn0rpUqVEnfC++CeAqaRWAf0v8uWLasVpzug73jlyhXt0deqVUvvJ1g946ygyvcGtMfQEsL2lylTRmdD3zvttoMKHq0TzPZwsb9//17vHdStW9f2NWg/bN++XStDvPfmzZv1HktB59TzYOXKlfL7779roOO6cQLHhjoqO9woxE7GSGi1XvIKwTR8+HDtlaPSt26gugMqMUy/sGwEM/r3eYGTCCGKm2Nos+BGG6br6NVjWo5erDX7QAXo7kAH9M9xLwFVJt4H/U2rr4ivOA6JiYn56lniQsBHwVChderUSY+HJ7YlN9DrR+hiwMxvmFvQMvn48aOGslVxo9WUXajjBjgG9vbt2+vPaIHhHgQ57zxISUmRX3/9Va8JqwWHghEzXF8KSMPV6zC4ANDPcsrIZwInfWYe62J93BN9Z8zI3DnIEvkDT33k2bGVOplrzZo1el8AszGc2OvWrfP1KhEZw5GVujfgkxmZP1OK9ofd1AmfR8/qkyDdunXTVojTOalSJyLxWKVeYEO9oGGoEzkL/8fTRETkn/+ZACIiyhuGOhGRQRjqREQGYagTERmEoU5EZBCGOhGRQRjqREQG4R8fEREZhJU6EZFBGOpERAZhqBMRGYShTkRkEIY6EZFBGOpERAZhqBMRGYShTkRkEIY6EZFBGOpERAZhqBMRGYShTkRkEIY6EZFBGOpERAZhqBMRGYShTkRkEIY6EZFBGOpERAZhqBMRGSTQ1ytA3vHmzRvuaiIHKVGihEeWy0qdiMggDHUiIoMw1ImIDMJQJyIyCEOdiMggDHUiIoMw1ImIDMJQJyIyCEOdiMggfh/qe/bskYkTJ+b4vJcvX8qiRYs8sg6XL1+WhISEDL8LDQ015q84Hzx4IOvXr8/2ORcvXpTIyEgpCBo0aKBfe/fuLXv37s3w2NixYyU+Pj7HZaR/3sKFC2XKlCk5vgbP27p1a57Xm9zrl19+0XOhZMmS8tdff4lT+HWof/nyRfr27SvLli1zXKjjd576M2Bve/jwoWzYsCHb49C0aVPZtGmTV9eLyJf69esnBw4ckKpVqzrqQDgy1AMCAmTGjBnSpEkTqV27dobqBI/Nnj1bWrRoIdOmTdMgwc6FY8eO6cg5btw4ady4sdSvX18uXLjgqoxQOaOCbt68ue17379/X0qXLq3v0axZM6lZs6bs37/f9vlPnz6VWbNmydGjR3XZeB9rPTGQQLVq1XR72rZtK1WqVJHVq1fLxo0bpU2bNvpY+gHh/Pnz0rlzZ11HbP+OHTv096mpqdK9e3dp2LChNGrUSKKiosQTPnz4oBU39i/WNzw8XCZMmCC3bt2SsLAwGTRokD4P+xnb3bFjRxkzZoycPHlSH7cqe2znggULpEOHDnoscPJb9u3bp9uH5WMZ2Ad4jS/huG/btk2uXbsm3759y/a55cqV+65lfv78Wc8j7CPsmxEjRsiLFy+yfc3Xr1/1XGnVqpX+mzx5snz69EkfK168uAQFBYlJUOXGxsbqPsK5vWXLFr85D8LCwqRSpUriNI79D3ohFC9duiR3797VAMAOxMUPhQsX1vCDzNXh9evXtVWwatUqDc/p06droOB7hC4q6Jy8evVKg3Pu3LmSnJws0dHROtXOSvny5WXevHmya9cu/Wfn3bt3cvr0abl9+7aevFivM2fO6HZg2YMHD9ZBYPTo0TqIVKxYUZ49e6YVMMIvKSlJqlevLgcPHtTlPX/+XDzh8OHDuh7W/sX7XL16VaZOnSqnTp3K8Fw8hsEMxwqhnnkfIvixnYcOHdL2Qo8ePXRwwqCL32HAxkXsqW3JjZCQEClWrJge77Nnz2qg1qlTRwoV+m/dc/z4cdf3KCxiYmJcPz969EiPL8TFxUlwcLAWG7B48WKZP3++LF261HY9MNijlXXixAk9zzGIok2DFuP48ePFREWLFtV9dPPmTQ13XAuBgYGOPw+cyrGhPmrUKP1ao0YNrfZwkluhPnLkSNvXobLGgQBUwqgCcgvVUP/+/V3LuHPnjuSXVeFi/bD8AQMG6M8YsBBqCFKEPgaxXr16ZXjtjRs3pHXr1tpmmjRpku6Pnj17iicgiHFxIUTatWunswM7w4YN00DPCrYRrTFo2bKl3Lt3T7/HYIH3QKDD0KFDdSZg59y5c/L48WPxFlReqKZxUR85ckQGDhwoFSpUsH0+Ar1Pnz6un62ZGqDf/vr1a73vA6i4c5qqI9ywXxF0gFnT2rVrv+u+kb+KiIjQrzgnEOZPnjz5TwXs9PPASRwb6pmlDw9MQ+2kn56i0kG/N7dwQVnvh2VgSpxfmdfL+hnvg39Yz7S0NG0ZIdyzglkGKumdO3fKzJkzdSaDZbkTZgO4gDCIogpHe8TuXgQqGm/uQ3+D47lkyRLp0qVLnpdhN2iaxBrAABVxXq5Z8oNQxzR0zpw52uPC1H758uX57t2hX4xqqUiRIm5bT2vZaDfkF9osqGgR3F27dnUFeb169SQlJUWrB1Q1qNLR9nn79q2UKlVK3Anvg3sKaAlhHdD/Llu2rFac7oBe/ZUrV7RHX6tWLb2fYPWMs4Iq3xvQHkNLCNtfpkwZnQ3ld9qNCh6tE8z20IZ5//693juoW7eu7WvQfti+fbtWhnjvzZs36z2Wgs6fzwNvc2yoo7LDjULs5BUrVrhaL3mFYBo+fLj2ylHpWzdQ3QGVGNo8WDaCGf37vMBJhBDFzTG0WXCjDdN19OoxLUcv1pp9oAJ0d6AD+ue4l4AqE++D/qbVV8RXHIfExMR89SxXrlwpQ4YM0QqtU6dOejw8sS25gV4/QhcDprsuYrRMPn78qKFsVdxoNWUX6rgBjoG9ffv2+jNaYLgHQc47D6Kjo/V+HdpFP/30k57Hf/75p88PVUAarl6HwQWAfhYqRnIPJ31mHutifdwTfWfMyNw5yBL5A0995NmxlTqZa82aNXpfALMxnNjr1q3z9SoRGcORlbo34JMZ+KOazO0P3By0+zx6Vp8E6datm7ZCnM5JlToRiccq9QIb6gUNQ53IWfg/niYiohz5z+d0iIgoRwx1IiKDMNSJiAzCUCciMghDnYjIIAx1IiKDMNSJiAzCPz4iIjIIK3UiIoMw1ImIDMJQJyIyCEOdiMggDHUiIoMw1ImIDMJQJyIyCEOdiMggDHUiIoMw1ImIDMJQJyIyCEOdiMggDHUiIoMw1ImIDMJQJyIyCEOdiMggDHUiIoMw1ImIDMJQJyIySKCvV4C8482bN9zVRA5SokQJjyyXlToRkUEY6kREBmGoExEZhKFORGQQhjoRkUEY6kREBmGoExEZhKFORGQQhjoRkUH8PtT37NkjEydOzPF5L1++lEWLFnlkHS5fviwJCQkZfhcaGmrMX3E+ePBA1q9fn+1zLl68KJGRkVIQNGjQQL/27t1b9u7dm+GxsWPHSnx8fI7LSP+8hQsXypQpU3J8DZ63devWPK83ud/t27ela9eu0qRJE/nxxx/l77//Fl/z61D/8uWL9O3bV5YtW+a4UMfvPPVnwN728OFD2bBhQ7bHoWnTprJp0yavrheRr02YMEGioqLk0qVLWlxisPY1R4Z6QECAzJgxQ0e/2rVrZ6hO8Njs2bOlRYsWMm3aNA2Sfv366WPHjh3TKmrcuHHSuHFjqV+/vly4cEEfw85G5YwKunnz5rbvff/+fSldurS+R7NmzaRmzZqyf/9+2+c/ffpUZs2aJUePHtVlWwcV64mBBKpVq6bb07ZtW6lSpYqsXr1aNm7cKG3atNHH0g8I58+fl86dO+s6Yvt37Nihv09NTZXu3btLw4YNpVGjRnoiecKHDx+04sb+xfqGh4friXvr1i0JCwuTQYMG6fOwn7HdHTt2lDFjxsjJkyf1cauyx3YuWLBAOnTooMfiwIEDrvfYt2+fbh+Wj2VgH+A1voTjvm3bNrl27Zp8+/Yt2+eWK1fuu5b5+fNnPY+wj7BvRowYIS9evMj2NV+/ftVzpVWrVvpv8uTJ8unTJ32sePHiEhQUJCYpWbKkxMbG6j7Cub1lyxa/OQ9SU1M1zK1rAtdKSkqK3LlzR3zJsf9BL4Qidtjdu3c1AHBR4OKHwoULa/hB5urw+vXr2ipYtWqVhuf06dM1UPA9QhcVdE5evXqlwTl37lxJTk6W6OhonWpnpXz58jJv3jzZtWuX/rPz7t07OX36tE7XcPJivc6cOaPbgWUPHjxYB4HRo0frIFKxYkV59uyZVsAIv6SkJKlevbocPHhQl/f8+XPxhMOHD+t6WPsX73P16lWZOnWqnDp1KsNz8RgGMxwrhHrmfYjgx3YeOnRI2ws9evTQCwGDLn6HARsXsae2JTdCQkKkWLFierzPnj2rgVqnTh0pVOi/dc/x48dd36OwiImJcf386NEjPb4QFxcnwcHBWmzA4sWLZf78+bJ06VLb9cBgj1bWiRMn9DxHYKBNgypw/PjxYqKiRYvqPrp586aGO66FwMBAx58H//zzj/zwww+udcV1ULlyZf39//73P/EVx4b6qFGj9GuNGjW02sNJboX6yJEjbV+HyhoHAlAJowrILVRD/fv3dy3DHSOvNZpj/bD8AQMG6M8YsBBqCFKEPgaxXr16ZXjtjRs3pHXr1tpmmjRpku6Pnj17iicgiHFxIUTatWunswM7w4YN0xM5K9hGtMagZcuWcu/ePf0egwXeA4EOQ4cO1ZmAnXPnzsnjx4/FWypVqqTVNC7qI0eOyMCBA6VChQq2z0eg9+nTx/Vz+uk3+u2vX7/W+z6Airtq1arZvj/CDfsVQQeYNa1du/a77hv5q4iICP2KcwIB+eTJEz0O/nQeOIljQz2z9OGBaaid9NNTVDro9+YWLijr/bAMTInzK/N6WT/jffAP65mWlqYtI4R7VjDLQCW9c+dOmTlzps5ksCx3wmwAFxAGUVThaI/Y3YtARePNfehvcDyXLFkiXbp0yfMy7AZNk1gDGKAizss16wuVK1fWAQjri8EIxxtVOn7vS44NdUxD58yZoz0uTO2XL1+e794d+sWolooUKeK29bSWjXZDfqHNgooWwY076laQ16tXT3t1qB5Q1aBKR9vn7du3UqpUKXEnvA/uKaAlhHVA/7ts2bJacboDevVXrlzRHn2tWrX0foLVM84KqnxvQHsMLSFsf5kyZXQ2ZDft/l6o4NE6wWwPbZj379/rvYO6devavgbth+3bt2tliPfevHmz3mMp6Jx4HoSEhOj9osTERJ1d7d69W69RX7ZeHB3qqOxwoxA7ecWKFa7WS14hmIYPH669clT61g1Ud0AlhjYPlo1gRv8+L3ASIURxcwxtFtxow3QdvXpMy9GLtWYfqADdHeiA/jnuJaDqwPugv2n1FfEVxwEncV7hQli5cqUMGTJEK7ROnTrp8fDEtuQGev0IXQyY+Q1zC1omHz9+1FC2Km60mrILddwAx8Devn17/RktMNyDIGeeB3Fxcdpyw/WP4g738nwtIA1Xr8PgAkA/CxUjuYeTPjOPdbE+7om+M2Zk7hxkifyBpz7y7NhKncy1Zs0avS+A2RhO7HXr1vl6lYiM4chK3RvwyQz8UU3m9gduDtp9Hj2rT4J069ZNWyFO56RKnYjEY5V6gQ31goahTuQs/B9PExGRf/5nAoiIKG8Y6kREBmGoExEZhKFORGQQhjoRkUEY6kREBmGoExEZhH98RERkEFbqREQGYagTERmEoU5EZBCGOhGRQRjqREQGYagTERmEoU5EZBCGOhGRQRjqREQGYagTERmEoU5EZBCGOhGRQRjqREQGYagTERmEoU5EZBCGOhGRQRjqREQGYagTERmEoU5EZBCGOhGRQRjqRERijv8D5XeNUQgrVJEAAAAASUVORK5CYII=", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from shared.diagram import make_frame, Stack\n", "from shared.diagram import diagram, adjust\n", "\n", "frames = []\n", "for n in [2,1,0]:\n", " d = dict(string='Hello', n=n)\n", " frame = make_frame(d, name='print_n_times', dx=1.3, loc='left')\n", " frames.append(frame)\n", "\n", "stack = Stack(frames, dy=-0.5)\n", "\n", "width, height, x, y = [3.53, 1.54, 1.54, 1.27]\n", "ax = diagram(width, height)\n", "bbox = stack.draw(ax, x, y)\n", "# adjust(x, y, bbox)" ] }, { "cell_type": "markdown", "id": "f2a83fdb", "metadata": {}, "source": [ "## Infinite recursion\n", "\n", "If a recursion never reaches a base case, it goes on making recursive\n", "calls forever, and the program never terminates. This is known as\n", "**infinite recursion**, and it is generally not a good idea.\n", "Here's a minimal function with an infinite recursion." ] }, { "cell_type": "code", "execution_count": null, "id": "5a97b504", "metadata": {}, "outputs": [], "source": [ "def recurse():\n", " recurse()" ] }, { "cell_type": "markdown", "id": "5a1eeeda", "metadata": {}, "source": [ "Every time `recurse` is called, it calls itself, which creates another frame.\n", "In Python, there is a limit to the number of frames that can be on the stack at the same time.\n", "If a program exceeds the limit, it causes a runtime error." ] }, { "cell_type": "code", "execution_count": null, "id": "2065d6b8", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Exception reporting mode: Context\n" ] } ], "source": [ "%xmode Context" ] }, { "cell_type": "code", "execution_count": null, "id": "411de9cb", "metadata": {}, "outputs": [], "source": [ "try:\n", " recurse()\n", "except RecursionError as error:\n", " print(type(error).__name__)\n" ] }, { "cell_type": "markdown", "id": "f51f6a47", "metadata": {}, "source": [ "The traceback indicates that there were almost 3000 frames on the stack when the error occurred.\n", "\n", "If you encounter an infinite recursion by accident, review your function to confirm that there is a base case that does not make a recursive call. And if there is a base case, check whether you are guaranteed to reach it." ] }, { "cell_type": "markdown", "id": "4814b9ec", "metadata": {}, "source": [ "## Recursion with return values\n", "\n", "Now that we can write functions with return values, we can write recursive functions with return values, and with that capability, we have passed an important threshold -- the subset of Python we have is now **Turing complete**, which means that we can perform any computation that can be described by an algorithm.\n", "\n", "To demonstrate recursion with return values, we'll evaluate a few recursively defined mathematical functions.\n", "A recursive definition is similar to a circular definition, in the sense that the definition refers to the thing being defined. A truly circular definition is not very useful:\n", "\n", "> vorpal: An adjective used to describe something that is vorpal.\n", "\n", "If you saw that definition in the dictionary, you might be annoyed. \n", "On the other hand, if you looked up the definition of the factorial function, denoted with the symbol $!$, you might get something like this: \n", "\n", "$$\\begin{aligned}\n", "0! &= 1 \\\\\n", "n! &= n~(n-1)!\n", "\\end{aligned}$$ \n", "\n", "This definition says that the factorial of $0$ is $1$, and the factorial of any other value, $n$, is $n$ multiplied by the factorial of $n-1$.\n", "\n", "```{figure} ../../images/fibonacci.png\n", ":width: 500px\n", ":name: fibonacci\n", "\n", "Fibonacci Sequence\n", "```\n", "\n", "If you can write a recursive definition of something, you can write a Python program to evaluate it. \n", "Following an incremental development process, we'll start with a function that take `n` as a parameter and always returns `0`." ] }, { "cell_type": "code", "execution_count": null, "id": "6775c707", "metadata": {}, "outputs": [], "source": [ "def factorial(n):\n", " return 0" ] }, { "cell_type": "markdown", "id": "e27558bd", "metadata": {}, "source": [ "Now let's add the first part of the definition -- if the argument happens to be `0`, all we have to do is return `1`:" ] }, { "cell_type": "code", "execution_count": null, "id": "83c8db78", "metadata": {}, "outputs": [], "source": [ "def factorial(n):\n", " if n == 0:\n", " return 1\n", " else:\n", " return 0" ] }, { "cell_type": "markdown", "id": "56dd12e4", "metadata": {}, "source": [ "Now let's fill in the second part -- if `n` is not `0`, we have to make a recursive\n", "call to find the factorial of `n-1` and then multiply the result by `n`:" ] }, { "cell_type": "code", "execution_count": null, "id": "1734868f", "metadata": {}, "outputs": [], "source": [ "def factorial(n):\n", " if n == 0:\n", " return 1\n", " else:\n", " recurse = factorial(n-1)\n", " return n * recurse" ] }, { "cell_type": "markdown", "id": "616d8f4c", "metadata": {}, "source": [ "The flow of execution for this program is similar to the flow of `countdown` in Chapter 5.\n", "If we call `factorial` with the value `3`:\n", "\n", "Since `3` is not `0`, we take the second branch and calculate the factorial\n", "of `n-1`\\...\n", "\n", "> Since `2` is not `0`, we take the second branch and calculate the\n", "> factorial of `n-1`\\...\n", ">\n", "> > Since `1` is not `0`, we take the second branch and calculate the\n", "> > factorial of `n-1`\\...\n", "> >\n", "> > > Since `0` equals `0`, we take the first branch and return `1` without\n", "> > > making any more recursive calls.\n", "> >\n", "> > The return value, `1`, is multiplied by `n`, which is `1`, and the\n", "> > result is returned.\n", ">\n", "> The return value, `1`, is multiplied by `n`, which is `2`, and the result\n", "> is returned.\n", "\n", "The return value `2` is multiplied by `n`, which is `3`, and the result,\n", "`6`, becomes the return value of the function call that started the whole\n", "process.\n", "\n", "The following figure shows the stack diagram for this sequence of function calls." ] }, { "cell_type": "code", "execution_count": null, "id": "007fa1ab", "metadata": {}, "outputs": [], "source": [ "from shared.diagram import Frame, Stack, make_binding\n", "\n", "main = Frame([], name='__main__', loc='left')\n", "frames = [main]\n", "\n", "ns = 3, 2, 1\n", "recurses = 2, 1, 1\n", "results = 6, 2, 1\n", "\n", "for n, recurse, result in zip(ns, recurses, results):\n", " binding1 = make_binding('n', n)\n", " binding2 = make_binding('recurse', recurse)\n", " frame = Frame([binding1, binding2], \n", " name='factorial', value=result,\n", " loc='left', dx=1.2)\n", " frames.append(frame)\n", " \n", "binding1 = make_binding('n', 0)\n", "frame = Frame([binding1], name='factorial', value=1, \n", " shim=1.2, loc='left', dx=1.4)\n", "frames.append(frame)\n", "\n", "stack = Stack(frames, dy=-0.45)" ] }, { "cell_type": "code", "execution_count": null, "id": "787cd816", "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAASYAAAD2CAYAAAB7jSpBAAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjcsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvTLEjVAAAAAlwSFlzAAAPYQAAD2EBqD+naQAAInJJREFUeJztnXmQVFf1xy8qPyCogKgQgySBACogYQmLLLIHZAlQ7DsqCpQEUgShoESWEPmDYt8CsqQgxEAS9k2WsAlKWMJSBCgWCYKQQAKILEbgV59Tvq6eYZbuN6973gzfT9VU93TPvNf97n3fe+65556T5+HDhw+dEEKEiK9k9wcQQojUSJiEEKFDwiSECB0SJiFE6JAwCSFCh4RJCBE6JExCiNAhYRJChA4JkxAidEiYhBChQ8IkhAgdEiYhROiQMAkhQoeESQgROiRMQojQIWESQoQOCZMQInRImIQQoUPCJIQIHRImIUTo+Fp2f4CcwL/+9a9Aj/eNb3wj0OMJkduQxSSECB0SJiFE6JAwCSFCh4RJCBE6cowwPf/884E7oYUQ4SSPSoRnjlblhMhlFlP9+vXdkCFDXL169VzJkiXd7373O7d+/XpXp04d98wzz7hJkyZF/vbVV191L7zwgllH/P3Jkycj7+XJk8ddv37dnvN/o0aNcrVq1XLPPvuse+211xL9NYQQuS2O6fz58+6DDz5wN2/eNFH54osv3K5du9ylS5dcuXLl3M9//nNXuHBhN2zYMDdx4kT7nz/96U9u0KBBbuPGjWkeE5Hau3evu3r1qitdurTr06ePe+qpp5LxdYQQuUGY2rdv77761a+6IkWKuFKlSrmWLVuaBYSQfOc733F///vfzUravHmzmz59uk2dHjx44D7//PN0j9m1a1d7/Pa3v23HPHfunIRJiFxCUoQpf/78kecIVOrf//vf/7pPPvnE/eY3v3EffvihWUBHjhyx6Vysx+QYQojcQWhW5W7cuOHy5s3rnnzySffw4UM3Y8aM7P5IQojHXZgqVqzoOnfu7MqXL28OcBzlQojHE4ULxIDCBYR4TC0mIYTw7fz+9NNPXdOmTVO8dvr0afMNFSxYMMXrrLDVrVvXJYvWrVubEz0aVgIJT0hNr1693CuvvJK0zyaEiB1N5WJAUznxOHL27Fm3e/du17BhQ1eiRImknltTOSFEmjADIsZw/vz5bs2aNe7OnTsuWUiYhBBpUqxYMdv2BQcPHnSzZs1yFy5ccMlAwiSEyHCva6FChez5v//9b7dw4UL3l7/8xWINE4l8TEKIDDl8+LBbuXJliteee+4517ZtW/fEE0+4RCCLSQiRIRUqVHikgMaZM2fc7Nmz3T//+U+XCCRMQogMYS8qaYqiYSrnTe3IHhI0EiYhRKZUrlzZFShQ4BFx+vLLL93ixYsDt5wkTEKITGGDPSt0pCtKDX6mr30t2EQlEiYhREz88Ic/jKzGeQL1ve99zw0cONDyqgWJhEkIERNFixZ13/zmN+05Ka2BLLS3bt1yQaNwASFEzCBEZJdli8of//hHd/HiRdsPy7aVIJHFJISIGaZu3r65mjVr2iP5+4MOuJQwCSF8QSERD/bUBYmESQjhe6WOMAL4+OOPH3n/3r17lse/TJkylqG2e/fu4SpGIITInZQsWdIdOnTI/eMf/3jkveHDh9vq3alTp+zx8uXLMR9XwiSE8A3l0yB1gCVR4aRLQbC80ILixYvHfFxN5YQQWRYmiM7XxF66b33rW+7111931apVs5W7rVu3xnxcCZMQwjfR9R3xKXlQ55E9dD/60Y/c/v373bRp01ynTp3clStXYjquhEkI4Zv79+9Hnv/f//1fCt/TV77yFdetWzf7HSc5QZlHjx6N6bgSJiGEb6KtpGhhYorXqFEjt2nTJvv93Llz9sO2lliQ81sI4Ruc3NHpUaKZM2eO+8UvfuGGDRtm1tMbb7zhnnrqqZiOK2ESQvjGK5fGJt7UmQdKlSrlPvjgA1/H1VROCOEbVt/gBz/4gQsSWUwJqh0nRE7kG6lS6GYEm3m9iG8v20BQyGISQvji+PHjkeff//73XZBImIQQcUM2gT//+c/2vF69espgKYQIh2/Jc3/UqFEj8OPLYhJCxAVR3StWrLDnL7zwQkJqy0mYhBBxsWPHDnf79m17/tOf/tQlAgmTECJmSKW7e/due96hQwdXsGBBlwgkTEKImCB7wJtvvmnP2VrCBt1EIWESQsTkV0KUKHAJLVu2dIlEwiSEyDQ04N13342kLOnXr19CHN6+hWnVqlVmwj3//PMxpy+IZvTo0e7u3bvOD+R0IZ9LZmzfvt0+n0ifl156yaqq1q5d27344ovu8OHDuly5hLt377ouXbpYmpGf/OQn1tbethG/okSGgJMnT9rvPXv2dMWKFXOJJq66cs2bN7cPxhf3dbI8edwXX3zhChcuHLcZGWsJYoRp8ODB7qOPPorrHI/TlpTr169H2mDNmjXuD3/4g9uzZ48LC/G0tx/YSgHseM+NwrRjxw7XtGlTu9/Y0Y9BsX79+ri3pHii9Le//c1+b9u2rfvxj3/skkHMLfPyyy9b/agRI0aYEpMAipSZfNAWLVqkSDS+bt06i2+oVKmSWS98Mcw/IMUmr3366af2065dO6ugUKFCBbuIHs8884ylS6hevbrr1atXCkuIjstIz/nLly/vunbtmiL9QqKhGunEiRNd/fr17bMvWbLEZSeUzlm6dKltEfBuuoyIHhhu3ryZZj36ZMM1HT9+vC0/Y1kzUFB6mmuMdUf/+89//hMputijRw+ra8Z748aNs9fpYzNnzowcc+TIkZbaFXikSkebNm0sIJD+OmTIEOtD9Geilz1rfsuWLXZj8xrn37lzp8sp7Zs/f367N7w25T70MgDEC9/bEyWMkmSJEsQ8LJEa88iRI2aN0LifffZZpF75hAkTrDORf4WKCH369LEvxY5jnGXEPPAewoO4eTcGUzNqU73//vsmUlWrVjUx8wrpXbt2zS4MFxlhis77QkNRshhVHzBggJs+fbpVZUgW+fLls8/E96Xzdu7cOaGjfEbQDizbbty40a4XNx7XPiOL4Fe/+pW1BeA/CAO0K6M9IESIDu1KGyNSs2fPdoMGDXJ9+/a1yq+LFy+2v7169WpMx9+3b58tdX/3u9+16Svn4jWu040bNyzRGcnMsCAJIEQsmQY1a9bMHTt2zNo8p7SvB9fsZz/7mfODVw68VatWrkqVKi6Z+L6TEAY6BqMMP15S8s2bN1tDemkQqD1VqFChNI/ByHTgwAF7TmfBeuI1T5h69+6d5mhOR508ebJZZlhPdCpGvWTSsWNHeyxbtqwJEo7B1Emw6PSM7smC8zNVpgOT+J04k/QqU8ydO9ce33rrLTdq1Cj33nvvuewGK8hj7dq1dv08C4ilaoTr1q1bbu/evZHI49QJ8TMCK4h+5lnk9B0GNax4+iw3Ov3v7NmzZiF48PqFCxfcc889l2PaF7Dq+S5M1/2An4qZDPdwsvElTIw6WFB0EBp69erV1rmzSmoR+vrXv56uKG7bts1GPFSdz8LvySR69KTj0slzIkzJX3nlFbNOsUCzk+hgPQYfBj6KJUaDMKUHA0T0VIcBM/qY0c8ZLLE+6MtYjmPGjHEbNmyw8zZo0MAtWLDA5WSmTZtmgoR/KSsraNkhSr6FCdXGSUZHZt4f7Rtifjt27Fh34sSJFFM5OgL/g3XjTeUaN27s5s2bZ74FpoZM6ZYvXx7T+RklESV8EYsWLbLk52ED/1gywL+GpUpUbpEiRcw3kp6pj+Mb6+PJJ5+MWCaU2eEnTBAnM2XKFDd16lQTHNr8888/d6VLl7bVRKZ4+Ii8qRz9gYyJngWO0HJNmGKnBf/D9SEvNdNCBIqVJ37HNcHUDWvBWxHGF5UT2hdmzJhh03NEKd6FprDgS5gwe3H44h9CnBAYLhpg7i5cuNAcjYgS5jf+JRqRjtSkSRNTcFImoOr9+/c3BzIjFc7KWHYqszLIRef8zL8xxSkV87iCqCP+3hQ6I98Dzm6uH9YEf8cNvWzZslA4wKPBz/P73//eRIjPiTgx4CFMTEOHDh1qfYoRHR8KfYepP98NEWGqlpaYeFCIET8WfZRKH7gP6Jscj0KN+LIQcAZenL7ZaUF9Fkf7ch+yQMX394Ig8Z35TXGbXcQVLpCbeZzCBYQIIoNlIsl9gRxCiByPhEkIETokTEKINCHW6+233445TixIVCVFCJEmLFIRQHz69OlIdHyywgdkMQkh0oQYMnIuERtGOAWrocmyniRMQoh0IQKecAMgjoyYxWRko5AwCSHShd0XTOOIc8NyYofDypUrLY7QSxqXCCRMQogMIZCVQOlosJqY2hGRnwgkTEKIDClQoIClT4neHUBcNtt+iJInMj1oJExCiEwhBU3qbUuIE1tlECe2OgWJhEkIEdNWFRI1pt6nhzjhhwo6G6jimKIuvBAifcj3f/DgwRSvsamYvFBBC5MsJiFETJCxgCwPTOmeffZZe430RolYnVN2ASFEXPnHiQgnXQ6paQgfSETqXVlMQoi4rCay1jJ1o3AEeAULgkTCJITwhVc1hUIiQcczSZiEEL4gtbVXgOPjjz9O8R4ZUqmmRLEOKh+RHZTNwLEiYRJC+MarHJNWkCUlwsijTpQ4FYF/+ctfxnxcCZMQwjde6azUOfcpvEkudi8ok5zqOM5jRcIkhPCNV/QWH1NG5QOodoPVFCsKsBRC+CaWmnWUZ8e/RJHOWJEwCSF8Q3krj7RKgFENmHqRVDiOp/CmhEkI4Zt79+6l+96kSZMsZziiFG/hTQmTECJLVYIh9V45CopS4JbqyJRch3z58sUcjClhEkL45pNPPrFHcoNHU6JEiQyd4ZmhVTkhhG+OHz9uj96m3qCQxfQ/VCJcCBdX+p87d+5YgYJECJMsJiGELw4cOBAJpozXuZ0ZEiYhRNyQ7sSLS2ratGmaoQJZQcIkhIibjz766JEsA0EiYRJCxAW+pXXr1tlzsgakLu0UBBImIURcrF271h6p0EtZp0QgYRJCxAx5l7wQgR49eri8efO6RCBhEkLExPXr192yZcvsOWXDCaJMFBImIURMfqXZs2fbc+rIedtMEoWESQiRaWjAokWLIpkE+vbta2WcQiNMq1atsqJ3VOQ8evRo3CcbPXq05QL2w/79+12nTp0y/bvt27fb5xNpw/Xv0qWLq1y5spnjJO86c+aMLlcuYejQoa5ChQqWj/vIkSNZPt6DBw/c8uXLreAA9O/f346daOISpjlz5rhRo0ZZDEPFihXjPtmYMWN8CROKXa1aNffOO+/E/b/iUXr37m0VVffs2WPpTwcOHBiqy0R7JxJuNn5yI23atHGbNm1yJUuWzPKx7t+/bz6lU6dO2e89e/a00k3JIGZhevnll92uXbvciBEjbKTt1q2biQXBVS1atHCXL1+O/C0xDiwjUh0B64VUB/369bP36tata6+hwPy0a9fORA6Vf+ONN1LUrxo2bJirXr2669WrVwpLiI774osv2vnLly/vunbtGkm/kAwYMUiAVb9+ffvsS5YscdkJuZSXLl1qqyWZ3XBsH+DaeZG6tJO3Qzw74ZqOHz/eapVhWbN3EcHkGteqVcv6nzeVuHTpkq0IkUea98aNG2ev08dmzpwZOebIkSMteyLw2L17d7txa9SoYf2VtBz0IfpzvXr1IoMm+YOIZuY1zr9z506XU9q3du3akcolWWXNmjVWTAA6duwY+H64jIh5ojht2jQzDQcPHmyNS1UEL9/vhAkTrDNhUaGuffr0scakrjnlg2/fvm3vITyIm7evhqlZuXLlLMMdIlW1alUTMzocXLt2zUSNmwhh8iCgi4YqWrSopVYYMGCAmz59uhs+fLhLFuSW4TPxfem8nTt3Tvi8Oz1oh4IFC7qNGzfa9eLG49rHUk8ehyZWUxigXXfs2GHPESJEh3aljREpPuugQYPMx9GwYUO3ePFi+9urV6/GdPx9+/a53bt326hP5Q7OxWtcpxs3blhczrlz56zC7IoVK0wsmeY2a9bMHTt2zNo8p7VvVihUqJA9MvCXKVPGJRPfdxLCQMdglOHHq5awefNma0guHBDn4H3B1DAyeRsB6SxYT7zmCRNTjrT24NBRJ0+ebJYZ1hOdilEvmTCCAHWzEKQrV648MlLR6RndkwXnJyk8HZh9TB06dHDFixdP9++x+s6ePWsjYxjACooO4uP6eRYQq0II161bt9zevXtNODy8vpcZWEHeVASLnL7DoIYVT5/lRqf/cU2aN28e+T9ev3DhQqRUUU5p36zCyludOnUSFqsUuDAx6mBB0UFo6NWrV5vvKaukFiGWJdMTxW3bttmIx6jGZ+H3ZBI9etJxE+0XCRquGYLEgkY8uZgTCVZB9ODDwJd6pEaY0oMBInqqw4AZfczo5wyWWB/0Zax4/J8bNmyw83JDLliwIMBvlnPJmw2i5FuYUG3ytjCVYt4f7RvCfzF27Fh34sSJFFM5OgL/g3XjTeUaN27s5s2bZ74FpoZM6VgBiOX8jJKIEr4IljKDcPYFDf6xZIB/DUv14sWLrkiRIuYbycjUnzFjhnv33XdNlIJOVxEULVu2dFOmTLGyPwgObU7un9KlS5sfhSkePiJvKkd/II2rZ4HjBuCaMMVOC/6H69OoUSObFiJQ+FP4HdcEUzf8nt6KML6onNK+uQFf3wyzF98QP54z2wNzd+HCheZoxF/EfNhzoNGR2PTnOb8ZtQlxx4HMKIWzkr/PDFYHEDvOj8nNZ3icQdS5HrQLCwWkOU2v09K5WcAgipebn5s80cFyfsDPg6Oez4evqXXr1hEn/dy5c92hQ4dMGHjfGxiZ+iM4iMivf/3rNMUkOic1vlKOTZ/jmtE3Eb758+ebLwv3AMeYNWuWyyntO2jQIBMt2rlt27Z2D+ZE8jzMSmLeXIQyWArh4spgmUhyry0ohMixSJiEEKFDwiSESBNivShYGWucWJCoSooQIk0IIyGA+PTp05Ho+GSFD8hiEkKkCTFkrAASG0Y4BauhybKeJExCiHQhHIetOkAcGaEZTPESjYRJCJEu7L5gGseuDCwndjisXLnSgnMJnk4UEiYhRIYQyJq6EgpWE1M7IvITgYRJCJEhBQoUsPQ40XtZictm2w9R8kSmB42ESQiRKWzdSb3JHnFiqwzidPPmTRckEiYhRExbVdjjmnqPHuKEHyroDcWKY4q68EKI9CHfPymZo2HDMHmhghYmWUxCiJgguR4paJjSeWl2SW+UiNU5ZRcQQsSVf5yIcPJfkZqG8IFWrVq5KlWquCCRxSSEiMtqImstUzcKRwCZQINGwiSE8AUVkoCkj0HHM0mYhBC+ILW1V4CDTLTRUOUG6wp/FHUo40XCJITwjVc5JnWQZfv27W3j79NPP+3ruAoXEEL4xiuddf78+RSvkyIlK8hiEkL4xit6i48pyPIBEiYhhG8SVZNQwiSE8A11JT3SqprtFwmTEMI39+7dc4lAwiSEyFKVYEi9V46CoyVKlLDColTn9lbvYkWrckII33jVkckNHo1XHdkvspiEEL45fvy4PXqbeoNCFtP/UIlwIVxc6X/u3LljBQoSIUyymIQQvjhw4IA95s+f3xUuXNgFiYRJCBE3pDvZunWrPW/atGmgoQIgYRJCxE30xlwvy0CQSJiEEHGBb2ndunX2vEmTJo+UdgoCCZMQIi7Wrl1rj1TopaxTIpAwCSFihrxLXohAjx49XN68eV0ikDAJIWLi+vXrbtmyZfacsuFEdicKCZMQIia/0uzZs+05deQaNGjgEomESQiRaWjAokWLIpkE+vbta2WcQiNMq1atsqJ3VOQ8evRo3CcbPXq0u3v3rvPD/v37XadOnTL9u+3bt9vnE2kzdOhQV6FCBcvXfOTIEV2mXMbQgNv3wYMHbvny5VZwAPr372/HTjRxCdOcOXPcqFGjLIahYsWKcZ9szJgxvoQJxa5WrZp755134v5fkZI2bdq4TZs2uZIlS4b20tDeiYSbjZ/cSJsA2/f+/fvmUzp16pT93rNnTyvdlAxiFiaqHuzatcuNGDHCHF/dunUzsSC4qkWLFu7y5cuRvyXGgWXESpUqmfVC3al+/frZe3Xr1rXXUGB+2rVrZyKHykfvSKbCwrBhw1z16tVdr169UlhCdFxSKXD+8uXLu65du0bSLyQDRoyJEye6+vXr22dfsmSJy+4ihEuXLrXVksxuuNq1a0cqW4QJrun48eOtVhmWNXsXBw4caNe4Vq1a1v+8qcSlS5dsRahmzZr23rhx4+x1+tjMmTMjxxw5cqR7/fXX7TmP3bt3txu3Ro0a1l+HDBlifYj+TI5qb9DcsmWLRTPzGuffuXOnexzbd82aNe7kyZP2vGPHjoHvh8uImCeK06ZNM9Nw8ODB1rhURfDy/U6YMME6ExYV6tqnTx9rTOqaUz749u3b9h7Cg7h5+2qYmpUrV869//77JlJVq1Y1MaPDwbVr10zUCHdHmDwI6KKhihYtanmGBwwY4KZPn+6GDx/ukkW+fPnsM/F96bydO3dO+Lw7PWiHggULuo0bN9r14sbj2gddTz7R0K47duyw5wgRokO70saIFM7XQYMGmY+jYcOGbvHixfa3V69ejen4+/bts8odjPqHDx+2c/Ea1+nGjRsWl3Pu3DmrMLtixQoTyzNnzrhmzZq5Y8eOWZs/Tu1bqFAhe2TgL1OmjEsmvu8khIGOwSjDj1ctYfPmzdaQXDggzsH7gqlhZPI2AtJZsJ54zROm3r17p7kHh446efJks8ywnuhUjHrJhBEEypYta4J05cqVR0YqOj2je7Lg/CSFpwOzj6lDhw6uePHiLqeAFRQdxMf18ywgVoUQrlu3brm9e/eacHh4fS8zsIK8qQgWOX2HQQ0rnj7LjU7/O3v2rGvevHnk/3j9woULjyQ7y+3t26BBA1enTp2ExSoFLkyMOlhQdBAaevXq1eZ7yiqpRYhlyfREcdu2bTbiMarxWfg9mUSPnnTcRPtFHgewCqIHHwa+1CM1wpQeDBDRUx0GzOhjRj9nsMT6oC9jxeP/3LBhg52XG3LBggUBfrOcS3aIkm9hQrXJ28JUinl/tG8I38/YsWPdiRMnUkzl6Aj8D9aNN5Vr3LixmzdvnvkWmBoypWMFIJbzM0oiSvgiWMoMozMX/1gywL+GpXrx4kVXpEgR843kxKlcNC1btnRTpkxxU6dONcGhzcn9U7p0afOjMMXDR+RN5egPpUqViljguAG4Jkyx04L/4fo0atTIpoUIFP4Ufsc1wdQNv6e3IowvKjVq38Thq+di9uIb4sdzZntg7i5cuNAcjfiLmA97DjQ6Epv+POc3lg4h7jiQGaVwVvL3mcHqAGLH+TG5+QyPM4g614N2YaGANKfpiRI+GkQLEWvbtq21URjBz0OeH0QIX1Pr1q0jaVznzp3rDh06ZMLA+97AyNQfwUFEyDmdlph4kIsaXynHps9xzeibCN/8+fPtOuEe4BizZs1y2clnubB9MyPPwyCr1OVglMFSCBdXBstEknNtfSFErkXCJIQIHRImIUSaEOv19ttvxxwnFiSqkiKESJMnnnjCAohPnz4diY5PVviALCYhRJoQQ8YKILFhhFOwGpos60nCJIRIF8Jx2KoDxJERmsEUL9FImIQQ6cLuC6Zx7MrAcmKHw8qVKy0FEsHTiULCJITIEAJZU1dCwWpiakdEfiKQMAkhMqRAgQKWxih6Lytx2Wz7IUqeyPSgkTAJITKFrTupN9kjTmyVQZxu3rzpgkTCJISIaasKe1xT79FDnPBDBb1hXHFMURdeCJE+5Ps/ePBgitfYMExeqKCFSRaTECImSK5HChqmdF6aXdIbJWJ1TtkFhBBx5R8nIpz8V6SmIXygVatWrkqVKi5IZDEJIeKymshay9SNwhFAJtCgkTAJIXxBhSQg6WPQ8UwSJiGEL0ht7RXgIBNtNFS5wbrCH0UdyniRMAkhfONVjkkdZNm+fXvb+Pv000/7Oq7CBYQQvvFKZ50/fz7F66RIyQqymIQQvvGK3uJjCrJ8gIRJCOEbQgcSgYRJCOEb6kp6pFU12y8SJiGEb+7du+cSgYRJCJGlKtCQeq8cBUdLlChhhUWpzu2t3sWKVuWEEL7xqiOTGzwarzqyX2QxCSF8c/z4cXv0NvUGhSym/6ES4bGh9DDC486dO1agIBHCJItJCOGLAwcO2GP+/Pld4cKFXZBImIQQcUO6k61bt9rzpk2bBhoqABImIUTcRG/M9bIMBImESQgRt29p3bp19rxJkyaPlHYKAgmTECIu1q5da49U6KWsUyKQMAkhYoa8S16IQI8ePVzevHldIpAwCSFi4vr1627ZsmX2nLLhRHYnCgmTECImv9Ls2bPtOXXkGjRo4BKJhEkIkWlowKJFiyKZBPr27WtlnEIjTKtWrbKid1TkPHr0aNwnGz16tLt7967zw/79+12nTp0y/bvt27fb5xPpc/r0ade4cWNXuXJlq3SROl+zEB4PHjxwy5cvt4ID0L9/f8v1nWjiqivXvHlz17NnT9elSxd/J8uTxzLdxRslimLHqtAI0+DBg+NOgP44bUlp2bKltWG3bt3cypUr3eTJk92OHTti+l9tSXl8uH//vonSyZMn7Xfu/aC3nmTZYqLqwa5du9yIESPM8UWnrlatmgVXtWjRwl2+fDnyt8Q4sIxYqVIls16oO9WvXz97r27duvYaCsxPu3btXMWKFV2FChVS7EimwsKwYcNc9erVXa9evVJYQggVqRQ4f/ny5V3Xrl0j6ReSASPGxIkTXf369e2zL1myxGV3EcKlS5faagkjXEaQNP7QoUMR6/Oll15yFy9edGfOnEnSpxU5hTVr1kREqWPHjkkTpbiEadq0aSYEjK579uxxU6ZMsenVkSNHTGyYpsGpU6dcnz593OLFi93hw4fdhx9+aPXN58yZY+8jblgzFM0bOHCgK1eunE0Lt23b5l577TX317/+NXLOa9eumai99dZbKT4LAV3ciJz/2LFjrlChQm769OkumeTLl8/E8r333nO//e1vTSyzM+9ywYIF3caNG92bb76ZoUCRH6dYsWIRCxQr1subI0Q03FfAwI8LJ5n49mAhDIgPPiN+vGoJmzdvds2aNTMxAuIcvC+Ymi1btkQ2AiJUWE+8VrNmTXutd+/eae7BYfaJQGKZIQg3btwwKy6ZMIJA2bJl7Sa/cuVKpMaWx759+9ylS5eS9pk4P1NlBIp9TB06dHDFixdP2vlF7qJBgwauTp06CYtVCnxVjnpRWFDr1683i2XSpEm+ndrRpBYhliXTE0UsLPwiWFuvvvpqIOeP12LyIHtfdlpM8YB1hIh6nxeRx1pKZEyKyLnkzQZR8m0xMSrjBC1atKgtIUb7hvD9jB071p04ccKspi+//NLdvn3brCb+B+vGc36zMjRv3jw3fvx48328//775myL5fxYaPh6cFqzlFmyZEkXNvCPJQP8a1iq+IqKFCliNb249qnTnXrTPnx/77zzjvkJWWnF0ipdunRSPqsQCbOYmKrhG+LHc2Z7kNt34cKFrnv37nYD1KhRI+JAGzJkiG3685zfWF0sVeNAxmwcOXKk/X1msDqA2HF+Vgr5DI8ziDrXg3ZhoYA0p2mJksfUqVPdggULLFyAKfGsWbOS+nmFCDRcIDfzOIULZAWFC4hkoMhvIUTokDAJIUKHhEkIETokTEKI0CFhEkKEDgmTECJ0SJiEEKFDwiSECB0SJiFE6JAwCSFCh4RJCBE6tFdOCBE6ZDEJIUKHhEkIETokTEKI0CFhEkKEDgmTECJ0SJiEEKFDwiSECB0SJiFE6JAwCSFCh4RJCBE6JExCiNAhYRJChA4JkxAidEiYhBChQ8IkhAgdEiYhROiQMAkhQoeESQgROiRMQggXNv4fsBaoDC2zqYsAAAAASUVORK5CYII=", "text/plain": [ "
" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "from shared.diagram import diagram, adjust\n", "\n", "width, height, x, y = [2.74, 2.26, 0.73, 2.05]\n", "ax = diagram(width, height)\n", "bbox = stack.draw(ax, x, y)\n", "# adjust(x, y, bbox)" ] }, { "cell_type": "markdown", "id": "f3073126", "metadata": {}, "source": [ "The return values are shown being passed back up the stack.\n", "In each frame, the return value is the product of `n` and `recurse`.\n", "\n", "In the last frame, the local variable `recurse` does not exist because the branch that creates it does not run." ] }, { "cell_type": "markdown", "id": "b5feafeb", "metadata": {}, "source": [ "## Fibonacci\n", "\n", "After `factorial`, the most common example of a recursive function is `fibonacci`, which has the following definition: \n", "\n", "$$\\begin{aligned}\n", "\\mathrm{fibonacci}(0) &= 0 \\\\\n", "\\mathrm{fibonacci}(1) &= 1 \\\\\n", "\\mathrm{fibonacci}(n) &= \\mathrm{fibonacci}(n-1) + \\mathrm{fibonacci}(n-2)\n", "\\end{aligned}$$ \n", "\n", "Translated into Python, it looks like this:" ] }, { "cell_type": "code", "execution_count": null, "id": "bcd67d93", "metadata": {}, "outputs": [], "source": [ "def fibonacci(n):\n", " if n == 0:\n", " return 0\n", " elif n == 1:\n", " return 1\n", " else:\n", " return fibonacci(n-1) + fibonacci(n-2)" ] }, { "cell_type": "markdown", "id": "7b33d0b4", "metadata": {}, "source": [ "If you try to follow the flow of execution here, even for small values of $n$, your head explodes.\n", "But according to the leap of faith, if you assume that the two recursive calls work correctly, you can be confident that the last `return` statement is correct.\n", "\n", "As an aside, this way of computing Fibonacci numbers is very inefficient.\n", "In the algorithms chapter I'll explain why and suggest a way to improve it." ] } ], "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.13.7" } }, "nbformat": 4, "nbformat_minor": 5 }