p1/predavanja/10b - Rekurzija - seznami.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rekurzivne funkcije na seznamih\n",
    "\n",
    "Tole je običajen način poučevanja rekurzije. Strinjam se z argumenti, zakaj je zgrešen. Vendar sem pogosto naletel na študente, ki jim je bilo tole lažje kot karkoli drugega. Zategadelj poskušam tudi tako; nekateri doživijo razsvetljenje po tej poti.\n",
    "\n",
    "\n",
    "## Palindrom\n",
    "\n",
    "Niz je palindrom, če se naprej in nazaj bere enako.\n",
    "\n",
    "Očitno obstaja kup načinov, da preverimo, ali je niz palindrom. Najlažji v Pythonu je, da ga pač obrnemo in pogledamo, ali ostane pri tem enak, `s[::-1] == s`.\n",
    "\n",
    "Vendar nas danes zanima rekurzivna rešitev. Zato se moramo najprej domisliti rekurzivne definicije palindroma: niz je palindrom, če sta prvi in zadnji znak enaka, vse, kar je vmes, pa je palindrom. Obenem moramo pristaviti, da so tudi prazni nizi palindromi.\n",
    "\n",
    "Kar smo napisali, \"*niz je palindrom, če je prazen ali pa je prvi znak enak zadnjemu in je vse, kar je vmes palindrom*\" dobesedno prevedemo v Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def palindrom(s):\n",
    "    return s == \"\" or s[0] == s[-1] and palindrom(s[1:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindrom(\"pericarežeracirep\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindrom(\"abcba\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindrom(\"abccba\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "palindrom(\"abcdba\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Študente tole pogosto zbega. Funkcija `palindrom` je definirana s funkcijo `palindrom`. Sama s sabo. Je to sploh dovoljeno? Deluje?\n",
    "\n",
    "Če bi napisali\n",
    "\n",
    "```python\n",
    "def palindrom(s):\n",
    "    return palindrom(s)\n",
    "```\n",
    "\n",
    "to seveda ne bi delovalo. Razlog, da gornje deluje, pa je v tem da je niz vedno krajši.\n",
    "\n",
    "- Ko se vprašamo, ali je `\"abccba\"` palindrom, funkcija ugotovi, da sta prvi in zadnji znak enaka in pokliče neko funkcijo, ki bo preverila, ali je `\"bccb\"` palindrom. Ta \"neka funkcija\" je slučajno ravno taista funkcija, a s tem ni nič narobe.\n",
    "- Funkcija, katere naloga je preveriti, ali je `\"bccb` palindrom, ugotovi, da sta prvi in zadnji znak enaka, nato pa pokliče neko funkcijo, ki bo preverila, ali je `\"cc\"` palindrom.\n",
    "- Funkcija, katere naloge je preveriti, ali je `\"cc\"` palindrom, ugotovi, da sta prvi in zadnji znak enaka, nato pa pokliče neko funkcijo, ki bo preverila, ali je `\"\"` palindrom.\n",
    "- Funkcija, katere naloge je preveriti, ali je `\"\"` palindrom, odgovori, da je.\n",
    "\n",
    "Kako Python zmore slediti temu? Kako se ne zgubi v tem, do kje je prišel, kaj preverja, kaj bo rezultat tega preverjanja? To naj vas ne skrbi. Zna pač. Da bi razložili, moramo vedeti več, kot bomo izvedeli pri tem predmetu.\n",
    "\n",
    "Funkcijam, ki kličejo same sebe, rečemo \"rekurzivne funkcije\".\n",
    "\n",
    "## Vsota elementov seznama\n",
    "\n",
    "Kako bi izračunali vsoto elementov seznama. Z zanko seveda znamo. Pa poskusimo še s trikom, kakršnega smo uporabili zgoraj. Za to spet potrebujemo rekurzivno definicijo vsote seznama - definicijo, ki se nanaša sama nase.\n",
    "\n",
    "Takole lahko rečemo: vsoto elementov seznama dobimo tako, da k prvemu elementu prištejemo vsoto ostalih. Če je seznam prazen, pa je vsota 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def vsota(s):\n",
    "    if not s:\n",
    "        return 0\n",
    "    return s[0] + vsota(s[1:])\n",
    "\n",
    "vsota([5, 8, 2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vsebuje seznam sama soda števila?\n",
    "\n",
    "Seznam vsebuje sama soda števila, če je prazen ali pa je prvi element sod in vsebuje preostanek seznama sama soda števila."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def soda(s):\n",
    "    return not s or s[0] % 2 == 0 and soda(s[1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soda([4, 8, 6, 1, 2, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "soda([4, 8, 6, 2, 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vsota sodih števil v seznamu\n",
    "\n",
    "Napisati želimo funkcijo, ki vrne vsoto vseh sodih elementov v podanem seznamu.\n",
    "\n",
    "Recimo tako:\n",
    "\n",
    "- Če je seznam prazen, je vsota enaka 0.\n",
    "- Če je ničti element sod, vrnemo vsoto ničtega elementa in vsote ostalih.\n",
    "- Sicer vrnemo le vsoto ostalih."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def vsota_sodih(s):\n",
    "    if not s:\n",
    "        return 0\n",
    "    if s[0] % 2 == 0:\n",
    "        return s[0] + vsota_sodih(s[1:])\n",
    "    else:\n",
    "        return vsota_sodih(s[1:])\n",
    "        \n",
    "vsota_sodih([4, 2, 5, 11, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prvi sodi element seznama\n",
    "\n",
    "Napisati želimo funkcijo, ki vrne prvi sodi element seznama.\n",
    "\n",
    "Če je ničti element sod, vrnemo tega. Sicer vrnemo prvega sodega med ostalimi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def prvi_sodi(s):\n",
    "    if s[0] % 2 == 0:\n",
    "        return s[0]\n",
    "    else:\n",
    "        return prvi_sodi(s[1:])\n",
    "        \n",
    "prvi_sodi([5, 11, 3, 4, 8, 7, 12])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ta funkcija ima manjšo težavo, kadar v seznamu ni nobenega sodega elementa. Ker prvi ni sod, išče sodega v preostanku. Ker prvi iz preostanka ni sod, išče sodega v preostanku. Ker prvi v tem preostanku ni sod ... in tako naprej, dokler ne pride do praznega seznama. Takrat bomo v prvi vrstici funkcije spraševali po prvem (no, ničtem) elementu, `s[0]` in Python bo javil napako, `Index out of range`.\n",
    "\n",
    "Recimo, da naj funkcija v takšnem primeru vrne `None`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "def prvi_sodi(s):\n",
    "    if not s:\n",
    "        return None\n",
    "    if s[0] % 2 == 0:\n",
    "        return s[0]\n",
    "    else:\n",
    "        return prvi_sodi(s[1:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Vsi sodi elementi seznama\n",
    "\n",
    "Funkcija, ki vrne vse sode elemente seznama je železna klasika napačnih rešitev. Tipični prvi poskus je"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def vsi_sodi(s):\n",
    "    if s == []:\n",
    "        return []\n",
    "    \n",
    "    t = []\n",
    "    if s[0] % 2 == 0:\n",
    "        t.append(s[0])\n",
    "    vsi_sodi(s[1:])\n",
    "    return t\n",
    "\n",
    "vsi_sodi([4, 2, 5, 11, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To ne deluje, ker vsaka funkcija naredi svoj seznam `t`, vanj doda en sem element in ga vrne. Na koncu dobimo le seznam, ki ga ustvari najbolj zunanja funkcija.\n",
    "\n",
    "V drugem poskusu poskusimo zagotoviti, da bodo vse funkcije uporabljale isti `t` tako, da ga postavimo pred funkcijo - tako da postane globalna spremenljivka."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = []\n",
    "\n",
    "def vsi_sodi(s):\n",
    "    if s == []:\n",
    "        return []\n",
    "    \n",
    "    if s[0] % 2 == 0:\n",
    "        t.append(s[0])\n",
    "    vsi_sodi(s[1:])\n",
    "    return t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To deluje - vendar le enkrat. Če tole poskusimo poklicati večkrat, bo funkcija vedno dodajale elemente v ta seznam - in to ne bo dobro."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 2, 6]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vsi_sodi([4, 2, 5, 11, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 2, 6, 4, 2, 6]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vsi_sodi([4, 2, 5, 11, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 2, 6, 4, 2, 6, 4, 2, 6]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "vsi_sodi([4, 2, 5, 11, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To lahko poskušamo rešiti na vse žive načine. Recimo tako, da seznam praznimo na začetku funkcije."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t = []\n",
    "\n",
    "def vsi_sodi(s):\n",
    "    t.clear()\n",
    "    \n",
    "    if s == []:\n",
    "        return t\n",
    "    \n",
    "    if s[0] % 2 == 0:\n",
    "        t.append(s[0])\n",
    "    vsi_sodi(s[1:])\n",
    "    return t\n",
    "\n",
    "vsi_sodi([4, 2, 5, 11, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To ne deluje, ker se seznam sprazni ob *vsakem* klicu. Obupani študenti potem pišejo maile, kako narediti, da se bo seznam spraznil samo prvič.\n",
    "\n",
    "Ne gre. Tu ni problem v tem, da ne znamo prav sprogramirati, temveč v tem, da narobe razmišljamo. Kakšna je rekurzivna definicija vseh sodih elementov seznama? To je seznam, ki vsebuje prvi element, če je le-ta sod, poleg tega pa vse sode elemente iz ostanka. Recimo tako:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "def vsi_sodi(s):\n",
    "    if s == []:\n",
    "        return []\n",
    "        \n",
    "    if s[0] % 2 == 0:\n",
    "        return [s[0]] + vsi_sodi(s[1:])\n",
    "    else:\n",
    "        return vsi_sodi(s[1:])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obstajajo tudi elegantnejši načini, obstajajo tudi hitrejši načini. A za nas je tale dovolj dober.\n",
    "\n",
    "## Sodolihi in lihosodi\n",
    "\n",
    "Seznam je sodolih, če se v njem izmenjujejo sodi in lihi elementi, začenši s sodim.\n",
    "\n",
    "Seznam je lihosod, če se v njem izmenjujejo lihi in sodi elementi, začenši z lihim.\n",
    "\n",
    "Napisati moramo funkciji `sodolih` in `lihosod`, ki preverita, ali je seznam tak, kot pravi ime funkcije."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sodolih(s):\n",
    "    return s == [] or s[0] % 2 == 0 and lihosod(s[1:])\n",
    "    \n",
    "def lihosod(s):\n",
    "    return s == [] or s[0] % 2 == 1 and sodolih(s[1:])\n",
    "    \n",
    "sodolih([4, 5, 8, 13, 2, 7, 0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tu vidimo primer, ko se dve funkciji kličeta med sabo. Tudi to je rekurzija in tudi za takšno obliko ni razloga, da ne bi delovala."
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}