python_lesson5_func_recursion/lesson5_part2_recursion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "<img src=\"../img/python_theme.png\">\n",
    "# MLClass. \"Прикладной анализ данных\"\n",
    "# Модуль \"Инструментарий Data Science\"\n",
    "<img src=\"../img/mlclass_logo.jpg\" height=\"240\" width=\"240\">\n",
    "\n",
    "## Автор материала: Юрий Кашницкий, ФКН НИУ ВШЭ\n",
    "</center>\n",
    "Материал распространяется на условиях лицензии <a href=\"https://opensource.org/licenses/MS-RL\">Ms-RL</a>. Можно использовать в любых целях, кроме коммерческих, но с обязательным упоминанием автора материала."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Урок 5. Функции. Рекурсия\n",
    "## Часть 2. Рекурсивные функции"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Python 2 and 3 compatibility\n",
    "# pip install future\n",
    "from __future__ import (absolute_import, division,\n",
    "                        print_function, unicode_literals)\n",
    "from builtins import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рекурсивная функция - это функция, которая в теле вызывает сама себя."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример.** Вычисление факториала (итеративная версия)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def factorial_iter(n):\n",
    "    k = 1\n",
    "    for i in range(2, n + 1):\n",
    "        k *= i\n",
    "    return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1\n",
      "2 2\n",
      "3 6\n",
      "4 24\n",
      "5 120\n",
      "6 720\n",
      "7 5040\n",
      "8 40320\n",
      "9 362880\n"
     ]
    }
   ],
   "source": [
    "for i, k in enumerate(range(1, 10)):\n",
    "    print(i+1, factorial_iter(k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Временная сложность - линейная по n. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 3.55 ms per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit factorial_iter(3200)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример.** Вычисление факториала (рекурсивная версия)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1\n",
      "2 2\n",
      "3 6\n",
      "4 24\n",
      "5 120\n",
      "6 720\n",
      "7 5040\n",
      "8 40320\n",
      "9 362880\n"
     ]
    }
   ],
   "source": [
    "def factorial_recur(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return n * factorial_recur(n-1)\n",
    "\n",
    "# n! = n * (n-1)!\n",
    "# 4! = 4 * 3 * 2 * 1 = 24\n",
    "for i, k in enumerate(range(1, 10)):\n",
    "    print(i+1, factorial_recur(k))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Временная сложность - линейная по n. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100 loops, best of 3: 4.98 ms per loop\n"
     ]
    }
   ],
   "source": [
    "from sys import setrecursionlimit\n",
    "setrecursionlimit(1000000)\n",
    "%timeit factorial_recur(3200)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример.** Вычисление элементов последовательности Фибоначчи (итеративная версия) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fib_iter(n):\n",
    "    a, b = 1, 1\n",
    "    for i in range(n):\n",
    "        a, b = b, a + b\n",
    "    return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, "
     ]
    }
   ],
   "source": [
    "for i in range(11):\n",
    "    print(fib_iter(i), end=\", \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Временная сложность - линейная по n. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100000 loops, best of 3: 2.71 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit fib_iter(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример.** Вычисление элементов последовательности Фибоначчи (рекурсивная версия) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fib_recur(n):\n",
    "    if n <= 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fib_recur(n - 1) + fib_recur(n - 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, "
     ]
    }
   ],
   "source": [
    "for i in range(11):\n",
    "    print(fib_recur(i), end=\", \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Временная сложность - экспоненциальная по n. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Доказательство** (метод математической индукции)\n",
    "\n",
    "Уравнение рекурии $T(n) = T(n-1) + T(n-2) + O(1)$. <a href=\"https://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5\">Обозначение O</a> - пояснение на Википедии\n",
    "\n",
    "$T(n \\leq 1) = O(1)$\n",
    "\n",
    "Пусть $T(n - 1) = O(2^{n-1})$\n",
    "\n",
    "Тогда $T(n) = T(n-1) + T(n-2) + O(1) = O(\\frac{2^{n}}{2}) + O(2^{n-2}) + O(1) = O(2^n)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loops, best of 3: 1min 22s per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit fib_recur(40)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример**. Метод сортировки QuickSort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def qs(a_list):\n",
    "    if len(a_list) <= 1:\n",
    "        return a_list\n",
    "    else:\n",
    "        el0 = a_list[0]\n",
    "        left, right = [], []\n",
    "        for elem in a_list[1:]:\n",
    "            if elem < el0:\n",
    "                left.append(elem)\n",
    "            else:\n",
    "                right.append(elem)\n",
    "        return qs(left) + [el0] + qs(right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "qs([9, 8, 7, 6, 5, 4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import choice\n",
    "\n",
    "def quick_sort(a_list):\n",
    "    if len(a_list) <= 1:\n",
    "        return a_list\n",
    "    pivot = choice(range(len(a_list)))\n",
    "    return quick_sort([i for i in a_list[:pivot] + a_list[pivot+1:] \n",
    "                       if i < a_list[pivot]]) + [a_list[pivot]] + \\\n",
    "           quick_sort([i for i in a_list[:pivot] + a_list[pivot+1:] \n",
    "                       if i >= a_list[pivot]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 6]"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "quick_sort([3, 4, 2, 1, 6])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Временная сложность - $O(n*log(n))$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000 loops, best of 3: 60.3 µs per loop\n"
     ]
    }
   ],
   "source": [
    "%timeit quick_sort([3, 4, 2, 1, 6, 145, 56, 23, 45, 234, 21])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Примеры дерева рекурсии QuickSort\n",
    "<img src=\"../img/qsort-recur1.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Опорный элемент - всегда нулевой\n",
    "<img src=\"../img/qsort-recur2.png\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "T(n) = 2*T(n/2) + O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "При случайном выборе опорного элемента\n",
    "<img src=\"../img/qsort_tree.gif\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Реализация, мимимизирующая потребление дополнительной памяти "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def sub_partition(array, start, end, idx_pivot):\n",
    "\n",
    "    'returns the position where the pivot winds up'\n",
    "\n",
    "    if not (start <= idx_pivot <= end):\n",
    "        raise ValueError('idx pivot must be between start and end')\n",
    "\n",
    "    array[start], array[idx_pivot] = array[idx_pivot], array[start]\n",
    "    pivot = array[start]\n",
    "    i = start + 1\n",
    "    j = start + 1\n",
    "\n",
    "    while j <= end:\n",
    "        if array[j] <= pivot:\n",
    "            array[j], array[i] = array[i], array[j]\n",
    "            i += 1\n",
    "        j += 1\n",
    "\n",
    "    array[start], array[i - 1] = array[i - 1], array[start]\n",
    "    return i - 1\n",
    "\n",
    "def quicksort_inplace(array, start=0, end=None):\n",
    "\n",
    "    if end is None:\n",
    "        end = len(array) - 1\n",
    "\n",
    "    if end - start < 1:\n",
    "        return\n",
    "\n",
    "    idx_pivot = random.randint(start, end)\n",
    "    i = sub_partition(array, start, end, idx_pivot)\n",
    "    #print array, i, idx_pivot\n",
    "    quicksort_inplace(array, start, i - 1)\n",
    "    quicksort_inplace(array, i + 1, end)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 6, 7]"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a_list = [3, 4, 2, 1, 6, 7]\n",
    "quicksort_inplace(a_list)\n",
    "a_list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Пример**. Простая визуализация бинарного дерева"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class BinaryTree:\n",
    "    def __init__(self, rootObj):\n",
    "        self.root = rootObj\n",
    "        self.leftChild = None\n",
    "        self.rightChild = None\n",
    "\n",
    "    def insertLeft(self, newNode):\n",
    "        if self.leftChild == None:\n",
    "            self.leftChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.leftChild = self.leftChild\n",
    "            self.leftChild = t\n",
    "\n",
    "    def insertRight(self,newNode):\n",
    "        if self.rightChild == None:\n",
    "            self.rightChild = BinaryTree(newNode)\n",
    "        else:\n",
    "            t = BinaryTree(newNode)\n",
    "            t.rightChild = self.rightChild\n",
    "            self.rightChild = t\n",
    "\n",
    "    def getRightChild(self):\n",
    "        return self.rightChild\n",
    "\n",
    "    def getLeftChild(self):\n",
    "        return self.leftChild\n",
    "\n",
    "    def setRootVal(self,obj):\n",
    "        self.root = obj\n",
    "\n",
    "    def getRootVal(self):\n",
    "        return self.root\n",
    "           \n",
    "    def __str__(self):\n",
    "        output = str(self.root)\n",
    "        if self.leftChild:\n",
    "            output = '/'.join([self.leftChild.__str__(), output]) \n",
    "        else:\n",
    "            output = '[' + output\n",
    "        if self.rightChild:\n",
    "            output = '\\\\'.join([output, self.rightChild.__str__()])     \n",
    "        else:\n",
    "            output = output + ']'\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Root: a\n",
      "Left child: [b]\n",
      "Tree: [b]/a\\[c]\n",
      "Tree: [d]/b\\[e]/a\\[c]\n",
      "Tree: [d]/b\\[e]/a\\[f]/c\\[g]\n"
     ]
    }
   ],
   "source": [
    "r = BinaryTree('a')\n",
    "r.insertLeft('b')\n",
    "r.insertRight('c')\n",
    "print(\"Root:\", r.getRootVal())\n",
    "print(\"Left child:\", r.getLeftChild())\n",
    "print(\"Tree:\", r)\n",
    "r.getLeftChild().insertLeft('d')\n",
    "r.getLeftChild().insertRight('e')\n",
    "print(\"Tree:\", r)\n",
    "r.getRightChild().insertLeft('f')\n",
    "r.getRightChild().insertRight('g')\n",
    "print(\"Tree:\", r)\n",
    "\n",
    "#      a\n",
    "#    /   \\\n",
    "#   b     c\n",
    "#  / \\   / \\\n",
    "# d   e f   g"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.10"
  },
  "name": "4_Functions.ipynb"
 },
 "nbformat": 4,
 "nbformat_minor": 0
}