{ "cells": [ { "cell_type": "markdown", "id": "starting-portfolio", "metadata": {}, "source": [ "# Recursion" ] }, { "cell_type": "markdown", "id": "further-brighton", "metadata": {}, "source": [ "A recursive algorithm is an algorithm that calls itself. You need a base case so you don't get stuck in an infinite loop." ] }, { "cell_type": "markdown", "id": "sunrise-cyprus", "metadata": {}, "source": [ "Example: suppose we want to calculate the quantity $n! = n(n-1)(n-2)\\cdots 3 \\cdot 2 \\cdot 1$." ] }, { "cell_type": "markdown", "id": "18459a42", "metadata": {}, "source": [ "5! = 5 * 4 * 3 * 2 * 1 = 120" ] }, { "cell_type": "markdown", "id": "gorgeous-girlfriend", "metadata": {}, "source": [ "We'll use the fact that $n! = n \\cdot (n-1)!$." ] }, { "cell_type": "code", "execution_count": 1, "id": "metallic-psychiatry", "metadata": {}, "outputs": [], "source": [ "# What's wrong with this function?\n", "def factorial(n):\n", " return n * factorial(n-1)" ] }, { "cell_type": "markdown", "id": "d6f39a51", "metadata": {}, "source": [ "py\n", "factorial(3)\n", " -> 3 * factorial(2)\n", " -> 3 * 2 * factorial(1)\n", " -> 3 * 2 * 1 * factorial(0)\n", " -> 3 * 2 * 1 * 0 * factorial(-1)\n", " -> infinite recursion\n", "" ] }, { "cell_type": "code", "execution_count": 3, "id": "appropriate-moore", "metadata": {}, "outputs": [ { "ename": "RecursionError", "evalue": "maximum recursion depth exceeded", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mRecursionError\u001b[0m Traceback (most recent call last)", "Input \u001b[0;32mIn [3]\u001b[0m, in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[43mfactorial\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m3\u001b[39;49m\u001b[43m)\u001b[49m\n", "Input \u001b[0;32mIn [1]\u001b[0m, in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mfactorial\u001b[39m(n):\n\u001b[0;32m----> 3\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m n \u001b[38;5;241m*\u001b[39m \u001b[43mfactorial\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m)\u001b[49m\n", "Input \u001b[0;32mIn [1]\u001b[0m, in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mfactorial\u001b[39m(n):\n\u001b[0;32m----> 3\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m n \u001b[38;5;241m*\u001b[39m \u001b[43mfactorial\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m)\u001b[49m\n", " \u001b[0;31m[... skipping similar frames: factorial at line 3 (2970 times)]\u001b[0m\n", "Input \u001b[0;32mIn [1]\u001b[0m, in \u001b[0;36mfactorial\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 2\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mfactorial\u001b[39m(n):\n\u001b[0;32m----> 3\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m n \u001b[38;5;241m*\u001b[39m \u001b[43mfactorial\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m)\u001b[49m\n", "\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded" ] } ], "source": [ "factorial(3)" ] }, { "cell_type": "markdown", "id": "31f6174b", "metadata": {}, "source": [ "What calls are happening?\n", "py\n", "" ] }, { "cell_type": "code", "execution_count": 4, "id": "failing-lounge", "metadata": {}, "outputs": [], "source": [ "# We need a base case!\n", "def factorial(n):\n", " if n == 1:\n", " return 1\n", " return n * factorial(n-1)" ] }, { "cell_type": "code", "execution_count": 5, "id": "acute-delicious", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "120" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factorial(5)" ] }, { "cell_type": "markdown", "id": "municipal-phoenix", "metadata": {}, "source": [ "py\n", "factorial(5)\n", "5 * factorial(4)\n", "5 * (4 * factorial(3))\n", "5 * (4 * (3 * factorial(2)))\n", "5 * (4 * (3 * (2 * factorial(1))))\n", "5 * (4 * (3 * (2 * 1)))\n", "" ] }, { "cell_type": "code", "execution_count": 6, "id": "functional-pointer", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "factorial(1000)" ] }, { "cell_type": "code", "execution_count": null, "id": "chinese-applicant", "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 }