{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Efficienza delle funzioni ricorsive e funzioni ausiliarie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consideriamo la funzione `palindroma_ricorsiva`, vista la lezione precedente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def palindroma_ricorsiva(s):\n",
    "    \"\"\"\n",
    "    Restituisce True se s è palindroma, False altrimenti\n",
    "    \"\"\"\n",
    "    if len(s) <= 1:      # caso base\n",
    "        return True\n",
    "    elif s[0] != s[-1]:  # casi ricorsivi\n",
    "        return False\n",
    "    else:\n",
    "        return palindroma_ricorsiva(s[1:len(s)-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Questa è invece la versione iterativa vista qualche tempo fa."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def palindroma_iterativa(s):\n",
    "    for i in range(len(s) // 2):\n",
    "        # confronta il carattere i-esimo a partire dall'inizio con il carattere\n",
    "        # i-esimo a partire dalla fine\n",
    "        if s[i] != s[- i - 1]:\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vorremmo confrontare le prestazioni di queste due funzioni. Un tale confronto andrebbe fatto con stringhe molto grandi, ma i limiti alla dimensione del call stack (pila dei recordi di attivazione) in Python ci limitano a stringhe di circa 6000 caratteri (perchè una palindroma di 6000 caratteri causa 3000 chiamate ricorsive prima di raggiungere il caso base, e 3000 è la dimensione massima del call stack in Python)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "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)",
      "Cell \u001b[0;32mIn[31], line 2\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[38;5;66;03m# La seguente istruzione fallisce\u001b[39;00m\n\u001b[0;32m----> 2\u001b[0m \u001b[43mpalindroma_ricorsiva\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[38;5;124;43ma\u001b[39;49m\u001b[38;5;124;43m\"\u001b[39;49m\u001b[43m \u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43m \u001b[49m\u001b[38;5;241;43m7000\u001b[39;49m\u001b[43m)\u001b[49m\n",
      "Cell \u001b[0;32mIn[9], line 10\u001b[0m, in \u001b[0;36mpalindroma_ricorsiva\u001b[0;34m(s)\u001b[0m\n\u001b[1;32m      8\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28;01mFalse\u001b[39;00m\n\u001b[1;32m      9\u001b[0m \u001b[38;5;28;01melse\u001b[39;00m:\n\u001b[0;32m---> 10\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[43mpalindroma_ricorsiva\u001b[49m\u001b[43m(\u001b[49m\u001b[43ms\u001b[49m\u001b[43m[\u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m:\u001b[49m\u001b[38;5;28;43mlen\u001b[39;49m\u001b[43m(\u001b[49m\u001b[43ms\u001b[49m\u001b[43m)\u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m]\u001b[49m\u001b[43m)\u001b[49m\n",
      "Cell \u001b[0;32mIn[9], line 10\u001b[0m, in \u001b[0;36mpalindroma_ricorsiva\u001b[0;34m(s)\u001b[0m\n\u001b[1;32m      8\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28;01mFalse\u001b[39;00m\n\u001b[1;32m      9\u001b[0m \u001b[38;5;28;01melse\u001b[39;00m:\n\u001b[0;32m---> 10\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[43mpalindroma_ricorsiva\u001b[49m\u001b[43m(\u001b[49m\u001b[43ms\u001b[49m\u001b[43m[\u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m:\u001b[49m\u001b[38;5;28;43mlen\u001b[39;49m\u001b[43m(\u001b[49m\u001b[43ms\u001b[49m\u001b[43m)\u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m]\u001b[49m\u001b[43m)\u001b[49m\n",
      "    \u001b[0;31m[... skipping similar frames: palindroma_ricorsiva at line 10 (2975 times)]\u001b[0m\n",
      "Cell \u001b[0;32mIn[9], line 10\u001b[0m, in \u001b[0;36mpalindroma_ricorsiva\u001b[0;34m(s)\u001b[0m\n\u001b[1;32m      8\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[38;5;28;01mFalse\u001b[39;00m\n\u001b[1;32m      9\u001b[0m \u001b[38;5;28;01melse\u001b[39;00m:\n\u001b[0;32m---> 10\u001b[0m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[43mpalindroma_ricorsiva\u001b[49m\u001b[43m(\u001b[49m\u001b[43ms\u001b[49m\u001b[43m[\u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m:\u001b[49m\u001b[38;5;28;43mlen\u001b[39;49m\u001b[43m(\u001b[49m\u001b[43ms\u001b[49m\u001b[43m)\u001b[49m\u001b[38;5;241;43m-\u001b[39;49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m]\u001b[49m\u001b[43m)\u001b[49m\n",
      "\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded"
     ]
    }
   ],
   "source": [
    "# La seguente istruzione fallisce\n",
    "palindroma_ricorsiva(\"a\" * 7000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fortunatamente, è possibile aumentare la dimensione dell call stack in Python, con la funzione `setrecursionlimit` del modulo `sys`. Notare che impostare un limite troppo grande potrebbe causare un crash dovuto all'esaurimento della memoria."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Fissa il limite a 1000000 per la dimensione del call stack\n",
    "\n",
    "from sys import setrecursionlimit\n",
    "setrecursionlimit(1_000_000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Adesso la stessa istruzione di prima ha successo\n",
    "palindroma_ricorsiva(\"a\" * 7000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Proviamo quindi a vedere il tempo di esecuzione della versione ricorsiva e iterativa, prima con una stinga lunga 50.000, poi una lunga 100.000."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "s1 = \"a\" * 50_000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6.65 ms ± 513 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "palindroma_iterativa(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "128 ms ± 20.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "palindroma_ricorsiva(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "s2 = \"a\" * 100_000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "18.1 ms ± 4.78 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "palindroma_iterativa(s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "434 ms ± 37.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "palindroma_ricorsiva(s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notiamo due cose:\n",
    "  1. `palindroma_ricorsiva` è più lenta di `palindroma_iterativa`. Questo è inevitabile:  per far funzonare la ricorsione, l'interprete Python deve salvare varie informazioni e deve mantenere la pila dei record di attivazione.\n",
    "  2. Raddoppiando la dimensione della stringa, il tempo che impiega  `palindroma_iterativa` raddoppia, ma quello che ci mette `palindroma_ricorsiva` quasi quadruplica. È un fenomeno che abbiamo visto quando abbiamo analizzato l'algoritmo di ordinamento per selezione: il termpo di esecuzione di `palindroma_ricorsiva` è quadratico rispetto alla lunghezza della stringa.\n",
    "\n",
    "Il problema al punto 2 è causato dal fatto che la funzione  `palindroma_ricorsiva` , ogni volta che richiama se stessa, deve prendere la stringa in input è generare una nuova stringa in cui ha tolto il primo e l'ultimo carattere. Questa nuova stringa occuperà nuovo spazio in memoria, che dipenderà dalla sua lunghezza (approssimativamente un byte ogni carattere). Inoltre, la creazione di questa stringa richiede anch'essa tempo, perché quella vecchia va copiata in una nuova zona di memoria (tranne, ovviamente, i due caratteri che vogliamo eliminare)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Per risolvere questo problema modifichiamo la funzione `palindroma_ricorsiva` in modo che prenda due parametri aggiuntivi (`first` e `last`). L'idea è che la nuova funziona non controlla se tutta la stringa in input è palindroma, ma solo se la parte compresa tra le posizioni `first` e `last` lo è. In pratica, la coppia `first` e `last` rappresentano una *finestra* sulla stringa sulla quale focalizzarsi (ricorda in questo l'algoritmo di ricerca binaria). In questo modo, quando dobbiamo richiamare la funzione ricorsivamente, non è necessario estrarre un sottostringa, ma possiamo semplicemente modificare gli estremi di questa *finestra*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def palindroma_ricorsiva_aux(s, first, last):\n",
    "    \"\"\"\n",
    "    Restituisce True se la parte di s compresta tra la posizione first e la posizione\n",
    "    last è palindroma, False altrimenti. Se first > last si intende che la parte\n",
    "    compresa tra first e last è vuota.\n",
    "    \"\"\"\n",
    "    if last <= first:          # caso base, la sottostringa che ci interessa ha lunghezza 0 oppure 1\n",
    "        return True\n",
    "    elif s[first] != s[last]:  # casi ricorsivi\n",
    "        return False\n",
    "    else:\n",
    "        # invece di richiamare \"palindroma_ricorsiva_aux\" su una porzione di \"s\" la\n",
    "        # richiamiamo su \"s\" stessa, ma restingiamo la finestra di osservazione eliminando\n",
    "        # il carattere in posizione \"first\" e quello in posizione \"last\"\n",
    "        return palindroma_ricorsiva_aux(s, first+1, last-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quando richiamiamo `palindroma_ricorsiva_aux` dobbiamo ricordarci di fornire anche i parametri `first` e `last`, pari normalmente a `0` e alla lunghezza della stringa meno 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindroma_ricorsiva_aux(\"osso\",0, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindroma_ricorsiva_aux(\"attenta\",0, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Poiché usare `palindroma_ricorsiva_aux` in questo è scomodo, spesso si definisce una funzione addizionale che fa da *interfaccia* tra `palindroma_ricorsiva_aux` e il programmatore. Il programmatore chiama questa funzione di interfaccia fornendo solo i parametri veramente necessari, gli altri vengono calcolati automaticamente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def palindroma_ricorsiva2(s):\n",
    "    # richiamo la funzione palindroma_ricorsiva_aux con i valori opportuni\n",
    "    return palindroma_ricorsiva_aux(s, 0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindroma_ricorsiva2(\"osso\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindroma_ricorsiva2(\"attenta\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Misuriamo i tempi di esecuzione della nuova versione."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13.2 ms ± 995 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "palindroma_ricorsiva2(s1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "26.5 ms ± 2.2 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "palindroma_ricorsiva2(s2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notiamo che:\n",
    "  1. Anche `palindroma_ricorsiva2` è più lenta di `palindroma_iterativa`, ma solo del doppio. \n",
    "  2. Raddoppiando la dimensione della stringa in input, il tempo di esecuzione di `palindroma_ricorsiva2` raddoppia, comportandosi bene, come la funzione iterativa, e non come quella ricorsiva non ottimizzata iniziale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Le torri di Hanoi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fin'ora abbiamo visto funzioni ricorsive che si potevano scrivere senza troppi problemi (anzi, spesso in maniera più intuitiva) in maniera ricorsiva. Ci sono però alcuni problemi che hanno soluzioni ricorsive molto semplici e soluzioni iterative estremamete complesse."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consideriamo il caso del gioco delle [torri di Hanoi](https://it.wikipedia.org/wiki/Torre_di_Hanoi). Secondo Wikipedia:\n",
    "<blockquote>\n",
    "La Torre di Hanoi   è un rompicapo matematico composto da tre paletti e un certo numero di dischi di grandezza decrescente, che possono essere infilati in uno qualsiasi dei paletti. Il gioco inizia con tutti i dischi incolonnati su un paletto in ordine decrescente, in modo da formare un cono. Lo scopo del gioco è portare tutti i dischi su un paletto diverso, potendo spostare solo un disco alla volta e potendo mettere un disco solo su un altro disco più grande, mai su uno più piccolo. \n",
    "</blockquote>\n",
    "\n",
    "Potete trovare una versione on-line del gioco su https://www.geogebra.org/m/fN74ZAsj"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Il nostro obiettivo è scrivere una funzione che, preso un numero `n` in input, stampi l'elenco delle mosse da fare per spostare `n` dischi dal piolo n. 1 al piolo n. 3. Scrivere un programma che stampi questo elenco può sembrare estremamente complicato. Tuttavi, supponiamo che ci sia un nostro amico che sa come spostare `n-1` dischi da un piolo ad un altro. Allora, per spostare `n` dischi dal piolo 1 al piolo 3 possiamo procedere come segue:\n",
    "  1. chiediamo all'amico di spostare `n-1` dischi  dal piolo 1 al 2;\n",
    "  2. spostiamo l'ultimo disco rimastro nel piolo 1 (il disco più grande di tutti) al piolo 3;\n",
    "  3. chiediamo di nuovo al nostro amico di spostare `n-1` dischi, questa volta dal piolo 2 al piolo 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Possiamo trasformare la sequenza di punti qui sopra nel caso ricorsivo di una funzione che risolve il nostro problema. Ma dobbiamo generalizzare la nostra funzione facendogli pendere due ulteriori parametri che sono il piolo di partenza e il piolo di arrivo dello spostamento. Come caso base consideriamo il problema in cui vogliamo spostare zero pioli: in questo caso, ovviamente, l'elenco degli spostamenti da compiere è vuoto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hanoi(n, from_peg, to_peg):\n",
    "    \"\"\"\n",
    "    Stampa la sequenza di operazioni necessarie per spostare \"n\" dischi dal piolo \"from_peg\" al piolo \"to_peg\".\n",
    "    I valori di \"from_peg\" e \"to_peg\" devono essere diversi tra di loro, e possono valere 1, 2 o 3.\n",
    "    \"\"\"\n",
    "    if n == 0:  # caso base, nulla da stampare\n",
    "        return\n",
    "    # from_peg e to_peg sono i pioli di partenza e destinazione (devono essere diversi).\n",
    "    # quando chiamiamo ricorsivamente la funzione hanoi, dobbimo spostare n-1 dischi dal\n",
    "    # piolo from_peg ad un piolo temporaneo, e poi dal piolo temporaneo a to_peg. Il piolo\n",
    "    # temporaneo è quello diverso sia da from_peg che da to_peg. L'istruzine if che segue\n",
    "    # determina il piolo temporaneo.\n",
    "    if from_peg != 1 and to_peg != 1:\n",
    "        tmp_peg = 1\n",
    "    elif from_peg != 2 and to_peg != 2:\n",
    "        tmp_peg = 2\n",
    "    else:\n",
    "        tmp_peg = 3\n",
    "    # prima chiamata ricorsiva\n",
    "    hanoi(n-1, from_peg, tmp_peg)\n",
    "    # stampa l'istruzione per spostare l'ultimo piolo da from_peg a to_peg\n",
    "    print(from_peg, \"->\", to_peg)\n",
    "    # seconda chiamata ricorsiva\n",
    "    hanoi(n-1, tmp_peg, to_peg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Poiché denotiamo i tre pioli con i numeri 1, 2 e 3, osserviamo che:\n",
    "  1. la somma di questi tre numeri fa 6\n",
    "  2. se calcoliamo `6 - from_peg - to_peg` otteniamo il piolo temporaneo da usare, al posto dell'if multiplo di prima.\n",
    "\n",
    "Usando questo metodo per calcolare `tmp_peg` otteniamo la seguente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hanoi(n, from_peg, to_peg):\n",
    "    \"\"\"\n",
    "    Stampa la sequenza di operazioni necessarie per spostare\n",
    "    \"n\" dischi dal piolo \"from_peg\" al piolo \"to_peg\".\n",
    "    \"\"\"\n",
    "    if n == 0:  # caso base, nulla da stampare\n",
    "        return\n",
    "    # determina il piolo temporaneo\n",
    "    tmp_peg = 6 - from_peg - to_peg\n",
    "    # prima chiamata ricorsiva\n",
    "    hanoi(n-1, from_peg, tmp_peg)\n",
    "    # stampa l'istruzione per spostare l'ultimo piolo da from_peg a to_peg\n",
    "    print(from_peg, \"->\", to_peg)\n",
    "    # seconda chiamata ricorsiva\n",
    "    hanoi(n-1, tmp_peg, to_peg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "E queste sono le istruzioni per risolvere il problema delle torri di Hanoi con 4 dischi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 -> 2\n",
      "1 -> 3\n",
      "2 -> 3\n",
      "1 -> 2\n",
      "3 -> 1\n",
      "3 -> 2\n",
      "1 -> 2\n",
      "1 -> 3\n",
      "2 -> 3\n",
      "2 -> 1\n",
      "3 -> 1\n",
      "2 -> 3\n",
      "1 -> 2\n",
      "1 -> 3\n",
      "2 -> 3\n"
     ]
    }
   ],
   "source": [
    "hanoi(4, 1, 3)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.12.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}