{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Функции\n",
    "## 1. Основные сведения и примеры"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Функция** — это обособленный участок кода, который можно вызывать, обратившись к нему по имени, которым он был назван. При вызове происходит выполнение команд *тела* функции. \n",
    "\n",
    "Функции можно сравнить с небольшими программками, которые сами по себе, т. е. автономно, не исполняются, а встраиваются в обычную программу. Нередко их так и называют – *подпрограммы*. \n",
    "\n",
    "С точки зрения Python функция — это объект, принимающий аргументы и возвращающий значение. В отличие от основной программы функции обычно получают данные не с устройства ввода (клавиатуры, файла и др.), а из вызывающей программы. Сюда же они возвращают результат своей работы.\n",
    "\n",
    "Вы уже знакомы с *встроенными* функциями, например, `input`, `abs`, `min`, `print` и т.д. Сейчас речь пойдет о тех функциях, которые может создавать программист.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# синтаксис описания функции\n",
    "def add2(x, y, z):\n",
    "    result = x**2 + y**2 + z**2\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "30\n"
     ]
    }
   ],
   "source": [
    "print(add2(1,2,5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В предыдущем примере `add2`— имя функции, `x, y, z` — аргументы функции. В данном случае функция вычисляет (или, как говорят, ***возвращает***) сумму квадратов своих аргументов.\n",
    "\n",
    "Используем функцию `add2` для решения задачи:\n",
    "\n",
    "|  Найти значение выражения |\n",
    "|---|\n",
    "$$y = -7\\frac{\\sqrt[3]{a^2+b^2+c^2}}{a^2 + (b-a)^2+\\frac{c^2}{4}}$$\n",
    "при следующих значениях переменных:\n",
    "$a=3, b=4, c=10$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1.0\n"
     ]
    }
   ],
   "source": [
    "a, b, c = 3, 4, 10\n",
    "y = -7*add2(a, b, c)**(1/3) / add2(a, b-a, c/2)\n",
    "print(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1.0\n"
     ]
    }
   ],
   "source": [
    "y = -7*(a**2 + b**2 + c**2)**(1/3) / (a**2 + (b-a)**2 + (c/2)**2) \n",
    "print(y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Аргументы и параметры, или Немножко филологии**\n",
    "\n",
    "*Математика*:\\\n",
    "$y = f(x)$   \n",
    "$x$ – аргумент, а $y$ – значение функции $f$.\n",
    "\n",
    "*Программирование*:\n",
    "```python\n",
    "def f(t):\n",
    "    return t**5\n",
    "y = f(x)\n",
    "```\n",
    "`t` – параметр (формальный параметр) функции `f`  \n",
    "`x` – аргумент (фактический параметр) функции `f`  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Функция может быть любой сложности и возвращать любые объекты (числа, логические значения, строки, списки, кортежи, и даже функции). Функция может и не заканчиваться инструкцией `return`, при этом функция вернет значение `None`.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример с функцией `add2` выше не очень показателен — использование функции не привело к заметному *упрощению* или *сокращению* кода.\\\n",
    "Рассмотрим другой пример. \n",
    "\n",
    "**Задача**. Даны длины четырех отрезков: $a$, $b$, $c$, $d$. Сколько есть возможностей выбрать три из них так, чтобы можно было сложить треугольник?\n",
    "\n",
    "\n",
    "Начинаем перебирать варианты: \\\n",
    "$a$, $b$, $c$ \\\n",
    "$a$, $b$, $d$ \\\n",
    "$a$, $c$, $d$ \\\n",
    "$b$, $c$, $d$\n",
    "\n",
    "Смотрим на код:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "a, b, c, d  = 1, 2, 3, 4\n",
    "k = 0\n",
    "if max(a, b, c) < a+b+c - max(a, b, c):\n",
    "    k += 1\n",
    "if max(a, b, d) < a+b+d - max(a, b, d):\n",
    "    k += 1\n",
    "if max(a, c, d) < a+c+d - max(a, c, d):\n",
    "    k += 1\n",
    "if max(b, c, d) < b+c+d - max(a, b, c):\n",
    "    k += 1    \n",
    "print(k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Читать такой код сложно. Явно видны повторы. Можно легко запутаться при разработке и при исправлении.\n",
    "\n",
    "Проще один раз написать правильную функцию и пользоваться ей:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "def is_3(a, b, c):\n",
    "    '''\n",
    "    функция возвращает True,\n",
    "    если из отрезков a, b, c\n",
    "    можно сложить треугольник\n",
    "    '''\n",
    "    return  max(a, b, c) < a+b+c - max(a, b, c)\n",
    "    \n",
    "k = is_3(a, b, c) + is_3(a, b, d) + is_3(a, c, d) + is_3(b, c, d)\n",
    "print(k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Польза функций не только в возможности многократного вызова одного и того же кода из разных мест программы. Не менее важно, что благодаря им программа приобретает **структуру**. Функции как бы разделяют ее на обособленные части, каждая из которых выполняет свою конкретную задачу. В результате код становится более *прозрачным*, его гораздо проще понимать, корректировать, находить и исправлять ошибки. Каждую функцию можно отлаживать отдельно, а потом из готовых работающих кирпичиков собирать программу.\n",
    "\n",
    "---\n",
    "Пусть надо написать программу, вычисляющую площади разных фигур. Пользователь указывает, площадь какой фигуры он хочет вычислить. После этого вводит исходные данные. Например, длину и ширину в случае прямоугольника. Поток выполнения разделяется на несколько ветвей с использованием оператора `if-elif-else`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "1-прямоуг., 2-треугольник, 3-круг:  1\n",
      "Ширина:  2\n",
      "Высота:  3\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Площадь: 6.0\n"
     ]
    }
   ],
   "source": [
    "figure = input('1-прямоуг., 2-треугольник, 3-круг: ')\n",
    "if figure == '1':\n",
    "    a = float(input('Ширина: '))\n",
    "    b = float(input('Высота: '))\n",
    "    print(f'Площадь: {a*b}')\n",
    "elif figure == '2':\n",
    "    a = float(input('Основание: '))\n",
    "    h = float(input('Высота: '))\n",
    "    print(f'Площадь: {0.5 * a * h}')\n",
    "elif figure == '3':\n",
    "    r = float(input('Радиус: '))\n",
    "    print(f'Площадь: {3.14 * r**2}')\n",
    "else:\n",
    "    print('Неопознанная фигура')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В принципе, и без функций все хорошо. Но что, если нам еще где-то в программе потребуется вычислять площадь круга? Или мы решим вычислять площадь треугольника не по высоте и основанию, а по трем сторонам (по формуле Герона, например)? Лучше написать функции! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "1-прямоуг., 2-треугольник, 3-круг:  2\n",
      "Основание:  1\n",
      "Высота:  1\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Площадь: 0.5\n"
     ]
    }
   ],
   "source": [
    "def rectangle():\n",
    "    a = float(input('Ширина: '))\n",
    "    b = float(input('Высота: '))\n",
    "    return a*b\n",
    "    \n",
    "def triangle():\n",
    "    a = float(input('Основание: '))\n",
    "    h = float(input('Высота: '))\n",
    "    return 0.5 * a * h\n",
    "\n",
    "def circle():\n",
    "    r = float(input('Радиус: '))\n",
    "    return 3.14 * r**2\n",
    "    \n",
    "figure = input('1-прямоуг., 2-треугольник, 3-круг: ')\n",
    "if figure == '1':\n",
    "    area = rectangle()\n",
    "elif figure == '2':\n",
    "    area = triangle()\n",
    "elif figure == '3':\n",
    "    area = circle()\n",
    "print(f'Площадь: {area}')    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Что может быть параметром функции?  \n",
    "**Всё!!!**  \n",
    "Параметром может быть любой объект, в том числе - функция.\n",
    "\n",
    "Еще один пример с вычислением математического выражения.\n",
    "\n",
    "|  Найти значение выражения |\n",
    "|---|\n",
    "$$\\frac{\\ln\\alpha + \\ln \\gamma + \\ln\\gamma^2}\n",
    "       {\\cos\\beta+ \\cos(\\beta+\\pi)+\\cos(\\beta-\\pi)}$$\n",
    "при следующих значениях переменных:\n",
    "$\\alpha=1, \\beta=\\pi, \\gamma = e$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.0\n"
     ]
    }
   ],
   "source": [
    "from math import cos, log, pi, e\n",
    "alpha = 1\n",
    "beta = pi\n",
    "gamma = e\n",
    "\n",
    "# аргумент функции - некоторая другая функция\n",
    "def add_f(f, a, b, c):\n",
    "    return f(a) + f(b) +f(c)\n",
    "\n",
    "z1 = add_f(log, alpha, gamma, gamma*gamma)\n",
    "z2 = add_f(cos, beta, beta+pi, beta-pi)\n",
    "print(z1/z2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Решение задач\n",
    "### Func1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Описать функцию `sign(x)` целого типа, <br>возвращающую для вещественного числа `x` следующие значения: \n",
    "$$\\left\\{\n",
    "\\begin{array}{ll}\n",
    "−1, &\\mbox{ если }x < 0; \\\\\n",
    "0, &\\mbox{ если }x = 0; \\\\\n",
    "1, &\\mbox{ если }x > 0 \n",
    "\\end{array}\n",
    "\\right.$$\n",
    "С помощью этой функции найти значение выражения `sign(a) + sign(b)` для данных вещественных чисел `a` и `b`. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# напишите текст функции ниже\n",
    "def sign(x):\n",
    "    if x>0:\n",
    "        return 1\n",
    "    elif x<0:\n",
    "        return -1\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sign(1)+sign(-2) = 0\n",
      "sign(1)+sign(25) = 2\n",
      "sign(-25)+sign(-25) = -2\n"
     ]
    }
   ],
   "source": [
    "# блок тестирования функции\n",
    "# тест 1\n",
    "a = 1\n",
    "b = -2\n",
    "print(f'sign({a})+sign({b}) = {sign(a)+sign(b)}')\n",
    "\n",
    "# тест 2\n",
    "a = 1\n",
    "b = 25\n",
    "print(f'sign({a})+sign({b}) = {sign(a)+sign(b)}')\n",
    "\n",
    "# тест 3\n",
    "a = -25\n",
    "b = -25\n",
    "print(f'sign({a})+sign({b}) = {sign(a)+sign(b)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# блок тестирования функции - 2\n",
    "assert sign(1)==1,   'Test 1'\n",
    "assert sign(10)==1,  'Test 2'\n",
    "assert sign(0)==0,   'Test 3'\n",
    "assert sign(-2)==-1, 'Test 4'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Func9."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Описать функцию `even(k)` логического типа, возвращающую `True`, если целый параметр `k` является четным, и `False` в противном случае. С ее помощью найти количество четных чисел в наборе из 10 целых чисел. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# напишите текст функции ниже\n",
    "def even(k):\n",
    "    return k%2 == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "# блок тестирования функции\n",
    "integers10 = 1, 121, 14, 24, 23, 565, 1, 11, 0, -5\n",
    "k = 0\n",
    "for n in integers10:\n",
    "    if even(n):\n",
    "        k += 1\n",
    "print(k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Func15. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Описать функцию `digit_n(k, n)` целого типа, возвращающую `n`-ю цифру целого положительного числа `k` (цифры в числе нумеруются справа налево, правая цифра имеет номер 1). Если количество цифр в числе `k` меньше `n`, то функция возвращает −1. Для каждого из пяти данных целых положительных чисел `k1`, `k2`, …, `k5` вызвать функцию `digit_n` с параметром `n`, изменяющимся от 1 до 5. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# напишите текст функции ниже\n",
    "def digit_n(k, n):\n",
    "    k //= 10**(n-1)\n",
    "    if k==0:\n",
    "        return -1\n",
    "    return k%10\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "k=12345:\n",
      "5 4 3 2 1 \n",
      "k=54321:\n",
      "1 2 3 4 5 \n",
      "k=123:\n",
      "3 2 1 -1 -1 \n",
      "k=23405600:\n",
      "0 0 6 5 0 \n",
      "k=314159265:\n",
      "5 6 2 9 5 \n"
     ]
    }
   ],
   "source": [
    "# блок тестирования функции\n",
    "k1 = 12345\n",
    "k2 = 54321\n",
    "k3 = 123\n",
    "k4 = 23405600\n",
    "k5 = 314159265\n",
    "for k in k1,k2,k3,k4,k5:\n",
    "    print(f'{k=}:')\n",
    "    for n in range(1,6):\n",
    "        print(digit_n(k,n), end=' ')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Func19. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Описать функцию `fact(n)` целого типа, вычисляющую значение факториала \n",
    "$$n! = 1·2·…·n$$ \n",
    "(`n` > 0 — параметр целого типа). С помощью этой функции найти факториалы пяти данных целых чисел. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# напишите текст функции ниже\n",
    "def fact(n):\n",
    "    p = 1\n",
    "    for i in range(1, n+1):\n",
    "        p *= i\n",
    "    return p    \n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0! = 1\n",
      "5! = 120\n",
      "50! = 30414093201713378043612608166064768844377641568960512000000000000\n",
      "1! = 1\n",
      "8! = 40320\n"
     ]
    }
   ],
   "source": [
    "# блок тестирования функции\n",
    "n1 = 0\n",
    "n2 = 5\n",
    "n3 = 50\n",
    "n4 = 1\n",
    "n5 = 8\n",
    "for n in n1, n2, n3, n4, n5:\n",
    "    print(f'{n}! = {fact(n)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Func24. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Описать функцию `mean(x, y)`, вычисляющую среднее арифметическое $\\displaystyle\\frac{x+y}2$ и среднее геометрическое $\\sqrt{x\\cdot y}$ двух положительных чисел $x$ и $y$ и возвращающую результат в виде двух вещественных чисел (`x` и `y` — вещественные параметры). С помощью этой функции найти среднее арифметическое и среднее геометрическое для пар `(a, b)`, `(a, c)`, `(a, d)`, если даны `a`, `b`, `c`, `d`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# напишите текст функции ниже\n",
    "def mean(x, y):\n",
    "    a = (x+y)/2\n",
    "    g = (x*y)**0.5\n",
    "    return a, g\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(505.0, 100.0)\n",
      "25.0 20.0\n"
     ]
    }
   ],
   "source": [
    "# блок тестирования функции\n",
    "a = 10.0\n",
    "b = 1000.0\n",
    "c = 40.0\n",
    "d = 360.0\n",
    "print(mean(a,b))\n",
    "mean_a, mean_g = mean(a,c)\n",
    "print(mean_a, mean_g)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. Тонкие вопросы "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Ключевые и позиционные аргументы. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "25.0\n",
      "0.04\n"
     ]
    }
   ],
   "source": [
    "def velocity(distance, time):\n",
    "    return distance/time\n",
    "\n",
    "print(velocity(50, 2))\n",
    "print(velocity(2, 50))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Проблема**: глядя на код\n",
    "```python \n",
    "print(velocity(2, 50))\n",
    "```\n",
    "трудно вспомнить/понять, где тут время, а где - расстояние.  \n",
    "**Решение**:\n",
    "```python \n",
    "print(velocity(distance=2, time=50))\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.04\n",
      "25.0\n",
      "10.0\n"
     ]
    }
   ],
   "source": [
    "# поэкспериментируем\n",
    "print(velocity(distance=2, time=50))\n",
    "print(velocity(time=2, distance=50))\n",
    "print(velocity(50, time=5))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "# А так?\n",
    "v = velocity(20, distance=5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "# А так?\n",
    "v = velocity(time=20, 5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "# или так\n",
    "print(end='***', 'hello')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2  Значение по умолчанию\n",
    "\n",
    "Предположим, мы хотим написать функцию вычисления веса объекта, имеющего массу `m`. Из школьной физики известна формула веса $P = m g$, где $m$ &ndash; масса объекта, а $g$ &ndash; ускорение свободного падения. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def p(m, g):\n",
    "    return m*g"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Приведенная функция годится для любой планеты, главное &ndash; правильно задать величину ускорения свободного падения. Но если большинство программистов будут использовать эту функцию для вычисления веса объектов, находящихся на Земле, то хорошо бы освободить их от необходимости постоянно писать 9.81 в качестве значения параметра $g$. Делается это так:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "98100.0 38600.0\n"
     ]
    }
   ],
   "source": [
    "def p(m, g=9.81):\n",
    "    return m*g\n",
    "\n",
    "mass = 10000 # 10 тонн\n",
    "p_earth = p(mass) # вес одной тонны на Земле; использовано значение g=9.81\n",
    "p_mars = p(mass, 3.86) # вес одной тонны на Марсе\n",
    "print(p_earth, p_mars)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Число 3.86 &ndash; ускорение свободного падения на Марсе &ndash; найдено в табличке на [Википедии](https://ru.wikipedia.org/wiki/Ускорение_свободного_падения)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3  Функции с произвольным количеством аргументов\n",
    "Мы уже знакомы со стандартными функциями, количество аргументов у которых может быть любым:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-10 100 90 -110\n"
     ]
    }
   ],
   "source": [
    "a = min(1,2,3,-1,-2,-10,20,30) # 8 аргументов\n",
    "b = max(a*a, a+20, 25)         # 3 аргумента\n",
    "print(a, b, a+b, a-b)          # 4 аргумента"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "sum(1,2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Напишем функцию `summ`, которая вычисляет сумму всех своих аргументов, сколько бы их не было"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "14\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "def summ(*args):\n",
    "    s = 0\n",
    "    for x in args:\n",
    "        s += x\n",
    "    return s\n",
    "\n",
    "print(summ(1))\n",
    "print(summ(1,2))\n",
    "print(summ(1,3,10))\n",
    "print(summ())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А как написать ***хорошую*** функцию, вычисляющую среднее арифметическое своих аргументов?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mean(a, *args):\n",
    "    s = a\n",
    "    for x in args:\n",
    "        s += x\n",
    "    return s/(len(args)+1)    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.0"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mean(1,2,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# а так?\n",
    "mean()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Количество ключевых аргументов тоже может быть произвольным. Но чтобы работать с ними, нужно сначала познакомиться с такой структурой данных как словарь. Займемся этим позже..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Области видимости переменных"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Областью видимости** имени переменной называется та часть программного кода, в которой к переменной с этим именем гарантируется однозначный доступ. Под переменной в этом контексте понимаются все *именованные* объекты языка &ndash; собственно переменные, функции, объекты и т.д. Переменную можно использовать только в пределах ее области видимости. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Переменная _видна_ в том блоке, где она первый раз появилась или определена. В таблице ниже &ndash; _причины_ появления переменной:\n",
    "\n",
    "| Действие| Оператор |\n",
    "| :-- | :-- |\n",
    "|Присваивание| \t`x = value`|\n",
    "|Подключение модулей|`import module` <br> `from module import name`|\n",
    "|Определение функции| \t`def my_func():` <br>&nbsp;&nbsp;&nbsp;`    ...`\n",
    "|\n",
    "|Задание параметров функции| \t`def my_func(arg1, arg2,... argN):`<br>&nbsp;&nbsp;&nbsp;`    ...`|\n",
    "|Описание класса \t| `class MyClass:`<br>&nbsp;&nbsp;&nbsp;`    ...` |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Области видимости в Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"legb.png\" width=\"150\" align=left> \n",
    "\n",
    "\n",
    "  &nbsp; **L**ocal &ndash; локальная,\n",
    "  \n",
    "  &nbsp; **E**nclosing &ndash; объемлющая (другое название - nonlocal),\n",
    "  \n",
    "  &nbsp; **G**lobal &ndash; глобальная,\n",
    "  \n",
    "  &nbsp; **B**uilt-in &ndash; встроенная\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Локальная область видимости &ndash; это блок кода (или тело) любой функции. В ней находятся имена, которые вы определяете внутри функции. Эти имена будут видны только в пределах тела функции. Локальная область видимости создается при вызове функции, а не при ее определении, поэтому у вас будет столько же различных локальных областей, сколько различных вызовов функций произошло в программе. Каждый вызов приводит к созданию новой локальной области.\n",
    "\n",
    "* Объемлющая (или охватывающая, или нелокальная) область видимости &ndash; это локальная область видимости функции *с точки зрения* вложенной (описанной внутри нее) функции. В примере ниже переменная `a` будет создана в объемлющей области с точки зрения функции `g` и в локальной области с точки зрения функции `f`.\n",
    "\n",
    "```python\n",
    "def f(x):\n",
    "    a = 1\n",
    "    def g(z):   # пример вложенной функции\n",
    "        return z+2\n",
    "    return g(a+x)    \n",
    "```\n",
    "\n",
    "* Глобальная область видимости &ndash; это самая верхняя область в программе или модуле. Имена в этой области видны (т. е. доступны) всюду в программном коде.\n",
    "\n",
    "* Встроенная область видимости создается или загружается всякий раз, когда вы запускаете скрипт или открываете интерактивный сеанс. Эта область содержит такие имена как ключевые слова, функции, исключения и другие атрибуты, встроенные в Python. Имена из этой области также доступны всюду в программе. \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "global\n"
     ]
    }
   ],
   "source": [
    "x1 = 'global'\n",
    "def f():\n",
    "    def g():\n",
    "        print(x1)\n",
    "    g()\n",
    "\n",
    "f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "enclosing\n"
     ]
    }
   ],
   "source": [
    "def f():\n",
    "    x2 = 'enclosing'\n",
    "    def g():\n",
    "        print(x2)\n",
    "    g()\n",
    "\n",
    "f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "x2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f():\n",
    "    def g():\n",
    "        x3 = 'local'\n",
    "        print(x3)\n",
    "    g()\n",
    "\n",
    "f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f():\n",
    "    def g():\n",
    "        print(min)\n",
    "    g()\n",
    "\n",
    "f()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Еще раз.** Локальные переменные доступны только внутри тела функции. Попытка их использовать \"снаружи\" приводит к ошибке:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "def add(a,b):\n",
    "    local = a+b\n",
    "    print(f'{a}+{b}={local}')\n",
    "\n",
    "a = 5\n",
    "b = 10\n",
    "add(a,b)\n",
    "print(local)    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Механизмы устранения \"конфликтов\" имен**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Что выведет программа, 10 или 100?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "::::::> 100\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "z = 10\n",
    "def z_print():\n",
    "    z = 100\n",
    "    print(f'::::::> {z}')\n",
    "\n",
    "z_print()\n",
    "print(z)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В общем случае поиск переменной идет по схеме **L $\\to$ E $\\to$ G $\\to$ B**\n",
    "\n",
    "Но посмотрите на следующий пример. Почему при вызове второй функции возникает ошибка?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 100\n",
    "\n",
    "def x_print1():\n",
    "    print(f'х плюс 1 = {x+1}')\n",
    "\n",
    "def x_print2():\n",
    "    x = x+1\n",
    "    print(f'x плюс 1 = {x}')\n",
    "\n",
    "x_print1()\n",
    "x_print2()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Кроме правила поиска имени **L $\\to$ E $\\to$ G $\\to$ B** нужно помнить правила _появления_ переменных (Таблица выше). Если мы что-то присваиваем переменной внутри тела функции, переменная создается в этот момент, а значит, является локальной. Локальная переменная `x` внутри функции `x_print2` еще не имеет  значения, поэтому выражение `x + 1` не может быть вычислено."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**А если очень-очень нужно...** <br/>\n",
    "Может ли функция `x_print2` все-таки изменить значение глобальной переменной `x`? \n",
    "\n",
    "Да. Для этого используется описатель `global` в теле функции. В Python версии 3 появился ещё и описатель `nonlocal`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 100\n",
    "\n",
    "def x_print2():\n",
    "    global x\n",
    "    x = x+1\n",
    "    print(f'x плюс 1 = {x}')\n",
    "    \n",
    "x_print2()\n",
    "print(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Глобальные переменные и нелокальные переменные"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "# использование глобальной переменной\n",
    "def enclosing_f():\n",
    "    p = 20 \n",
    "    def local_f(x):\n",
    "        global  p\n",
    "        p += x\n",
    "        return p\n",
    "    print (f'Значение локальной функции: {local_f(1)}')\n",
    "\n",
    "p = 10 # используется это значение!\n",
    "enclosing_f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [],
   "source": [
    "# использование нелокальной переменной\n",
    "def enclosing_f():\n",
    "    p = 20 # используется это значение!\n",
    "    def local_f(x):\n",
    "        nonlocal p\n",
    "        p += x\n",
    "        return p\n",
    "    print (f'Значение локальной функции: {local_f(1)}')\n",
    "\n",
    "p = 10\n",
    "enclosing_f()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "no binding for nonlocal 'p' found (2355282250.py, line 7)",
     "output_type": "error",
     "traceback": [
      "\u001b[1;36m  Cell \u001b[1;32mIn[81], line 7\u001b[1;36m\u001b[0m\n\u001b[1;33m    nonlocal p\u001b[0m\n\u001b[1;37m    ^\u001b[0m\n\u001b[1;31mSyntaxError\u001b[0m\u001b[1;31m:\u001b[0m no binding for nonlocal 'p' found\n"
     ]
    }
   ],
   "source": [
    "# попытка объявления нелокальной переменной,\n",
    "# отсутствующей в объемлющей функции, \n",
    "# приводит к ошибке на этапе компиляции\n",
    "def enclosing_function():\n",
    "    q = 20\n",
    "    def local_function(x):\n",
    "        nonlocal p \n",
    "        p += x\n",
    "        return p\n",
    "    print (local_function(10))\n",
    "\n",
    "p = 10\n",
    "enclosing_function()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно ли придумать осмысленный пример, когда функция **должна** менять значение глобальной переменной?\n",
    "\n",
    "Да, один пример см. ниже. Таким же образом будет использована глобальная переменная при решении задачи **Recur4**. Однако существует общее мнение: по возможности лучше избегать использования глобальных переменных вообще, и их изменения внутри функции &ndash; в особенности. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Теперь у меня 6 конфет.\n",
      "Теперь у меня 7 конфет.\n",
      "Теперь у меня 8 конфет.\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "# Пример с изменением глобальной переменной\n",
    "def get_candy():\n",
    "    global candy \n",
    "    candy += 1\n",
    "    print(f'Теперь у меня {candy} конфет.')\n",
    "\n",
    "candy = 5\n",
    "get_candy()\n",
    "get_candy()\n",
    "get_candy()\n",
    "print(candy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Про области видимости, локальные и глобальные переменные можно ещё почитать, например, тут:<br>\n",
    "https://realpython.com/python-scope-legb-rule/ (на английском)<br>\n",
    "https://habr.com/ru/company/otus/blog/487952/ (на русском)<br>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Для закрепления.**\\\n",
    "Сколько раз будет выведено `x=20`, а сколько `x=10`?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [],
   "source": [
    "def f(x):\n",
    "    print(f'внутри f. 1: x={x}, id={id(x)}')\n",
    "    x = 10\n",
    "    print(f'внутри f. 2: x={x}, id={id(x)}')\n",
    "\n",
    "x = 20\n",
    "print(f'** вне f. 1: x={x}, id={id(x)}')\n",
    "f(x)\n",
    "print(f'** вне f. 2: x={x}, id={id(x)}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [],
   "source": [
    "# А если так?\n",
    "\n",
    "def f():\n",
    "    print(f'внутри f. 1: x={x}, id={id(x)}')\n",
    "    x = 10\n",
    "    print(f'внутри f. 2: x={x}, id={id(x)}')\n",
    "\n",
    "x = 20\n",
    "print(f'** вне f. 1: x={x}, id={id(x)}')\n",
    "f()\n",
    "print(f'** вне f. 2: x={x}, id={id(x)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Рекурсия\n",
    "\n",
    "<div align=right><em>\n",
    "    Чтобы понять рекурсию, <br/>нужно сначала понять рекурсию</em>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Мы видели, функция может вызывать *другую* функцию. Но функция также может вызывать и саму себя! Такой вызов называется **рекурсией**, а сама функция называется рекурсивной. \n",
    "\n",
    "Рассмотрим это на примере функции вычисления факториала. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recur1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Описать **рекурсивную** функцию `fact_r(n)` целого типа, вычисляющую значение факториала \n",
    "$$n! = 1·2·…·n$$ \n",
    "(`n` > 0 — параметр целого типа). С помощью этой функции найти факториалы пяти данных целых чисел. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рекурсивное определение факториала:\n",
    "$$\n",
    "  n! = (n-1)!\\cdot n\n",
    "$$\n",
    "$$\n",
    "  0! \\equiv 1\n",
    "$$  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "# напишите текст функции ниже\n",
    "def fact_r(n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    else:\n",
    "        return fact_r(n-1)*n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10! = 3628800\n",
      "5! = 120\n",
      "50! = 30414093201713378043612608166064768844377641568960512000000000000\n",
      "1! = 1\n",
      "8! = 40320\n"
     ]
    }
   ],
   "source": [
    "# блок тестирования функции\n",
    "nn = 10, 5, 50, 1, 8\n",
    "for n in nn:\n",
    "    print(f'{n}! = {fact_r(n)}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Некоторые выводы**<br/>\n",
    "* В описании рекурсивной функции должна присутствовать проверка условия, определяющего, по какой ветке пойдет вычисление: по рекурсивной — в этой ветке произойдёт вызов функцией себя самой, или **терминальной**, которая закончит вычисление и вернёт результат.\n",
    "* Отсутствие терминальной ветки или ошибки в реализации условия перехода на эту ветку приведут к зацикливанию программы. \n",
    "* К тестированию рекурсивных функций нужно относиться особенно ответственно. Особенно важно проверять срабатывание условия завершения рекурсии."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Знаменитая рекурсия** &ndash; но программировать так не надо :)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [],
   "source": [
    "def short_story():\n",
    "    print(\"У попа была собака, он её любил.\")\n",
    "    print(\"Она съела кусок мяса, он её убил,\")\n",
    "    print(\"В землю закопал,\")\n",
    "    print(\"Надпись написал, что\")\n",
    "    short_story()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Запускать на свой страх и риск!\n",
    "# В 99% случаев вызывает крах jupyter-сервера\n",
    "short_story()\n",
    "\n",
    "#Можно запустиь в IDLE - там не страшно, см. ниже про RecursionError"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В литературе рекурсия встречается довольно часто. Вот, например, цитата из Станислава Лема (\"Звездные дневники Ийона Тихого. Путешествие четырнадцатое\"), где главный герой ищет в энциклопедии, что такое ***сепульки***:          "
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "     Нашел следующие краткие сведения:\n",
    "     \"СЕПУЛЬКИ  -  важный  элемент цивилизации ардритов  (см.)  с  планеты\n",
    "Энтеропия (см.). См. СЕПУЛЬКАРИИ\".\n",
    "     Я последовал этому совету и прочел:\n",
    "     \"СЕПУЛЬКАРИИ - устройства для сепуления (см.)\".\n",
    "     Я поискал \"Сепуление\"; там значилось:\n",
    "     \"СЕПУЛЕНИЕ  - занятие ардритов (см.) с планеты Энтеропия  (см.).  См.\n",
    "СЕПУЛЬКИ\".\n",
    "     Круг  замкнулся, больше искать было негде.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Рекурсия без терминальной ветви имеет еще одно название &ndash; **порочный круг.** "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Глубина рекурсии. Стек. \n",
    "\n",
    "Существует предел глубины возможной рекурсии, который зависит от реализации Python. Когда предел достигнут, возникает исключение `RecursionError`.\n",
    "\n",
    "Сколько раз сработала функция в предыдущем примере? <br/> Чтобы узнать это, немножко откорректируем текст, убрав вывод на печать - из-за большого объема этого вывода и может произойти крах jupiter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [],
   "source": [
    "story_counter = 0\n",
    "def short_story():\n",
    "    global story_counter\n",
    "#     print(\"У попа была собака, он её любил.\")\n",
    "#     print(\"Она съела кусок мяса, он её убил,\")\n",
    "#     print(\"В землю закопал,\")\n",
    "#     print(\"Надпись написал, что\")\n",
    "    story_counter += 1\n",
    "    short_story()\n",
    "    \n",
    "short_story()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "story_counter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Узнать и/или изменить предел глубины рекурсии можно с помощью модуля `sys`:\n",
    "\n",
    "```python\n",
    "import sys\n",
    "sys.setrecursionlimit(limit)\n",
    "sys.getrecursionlimit()\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# покспериментируем здесь и потом снова вызовем функцию short_story:\n",
    "import sys\n",
    "sys.setrecursionlimit(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recur3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Описать рекурсивную функцию `power_n(x, n)` вещественного типа, находящую значение `n`-й степени числа `x` по формулам: \n",
    "$$\\small\n",
    "x^n=\\left\\{\\begin{array}{ll}\n",
    "1, &\\mbox{если }n=0,\\\\\n",
    "\\displaystyle\\left(x^{\\frac{n}2}\\right)^2, &\\text{при четных }n>0,\\\\\n",
    "\\displaystyle x\\cdot x^{n-1}, &\\text{при  нечетных }n>0,\\\\\n",
    "\\displaystyle 1/{x^{-n}}, &\\text{при } n<0\n",
    "\\end{array}\n",
    "\\right.\n",
    "$$\n",
    "($x \\neq 0$ — вещественное число, $n$ — целое; в формуле для четных $n$ должна использоваться операция целочисленного деления).\n",
    "\n",
    "С помощью этой функции найти значения $x^n$ для данного `x` при пяти данных значениях `n`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "# напишите текст функции ниже\n",
    "def power_n(x, n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    elif n<0:\n",
    "        return 1/power_n(x, -n)\n",
    "    elif n%2==0:\n",
    "        y = power_n(x, n//2)\n",
    "        return y*y\n",
    "    else:\n",
    "        return x*power_n(x, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# блок тестирования функции\n",
    "x = 2.0\n",
    "nn = -2, 0, 10, 5, 1000 \n",
    "for n in nn:\n",
    "    print(power_n(x, n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0715086071862673e+301"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2**1000.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recur 4."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Описать рекурсивную функцию `fib1(n)` целого типа, вычисляющую `n`-й элемент последовательности *чисел Фибоначчи* (`n` — целое число): \n",
    "$$f_1 = f_2 = 1, \\ f_k = f_{k-2} + f_{k-1}, \\    k = 3, 4, … .$$\n",
    "С помощью этой функции найти пять чисел Фибоначчи с данными номерами, и вывести эти числа вместе с количеством рекурсивных вызовов функции `fib1`, потребовавшихся для их нахождения. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "counter = 0\n",
    "# напишите текст функции ниже\n",
    "def fib1(n):\n",
    "    global counter\n",
    "    counter += 1\n",
    "    if n==1 or n==2:\n",
    "        return 1\n",
    "    else:\n",
    "        return fib1(n-2) + fib1(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "55 109\n",
      "610 1219\n",
      "6765 13529\n",
      "75025 150049\n",
      "832040 1664079\n"
     ]
    }
   ],
   "source": [
    "# блок тестирования функции\n",
    "nn =  10, 15, 20, 25, 30\n",
    "for n in nn:\n",
    "    counter = 0\n",
    "    print(fib1(n), counter)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Попробуем сделать вывод..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<font color=\"#0000FF\">\n",
    "\n",
    "**Связь рекурсии и стека**: задача «Разворот последовательности» c сайта http://pythontutor.ru <br>\n",
    "\n",
    "Дана последовательность целых чисел, заканчивающаяся числом 0. Выведите эту последовательность в обратном порядке. При решении этой задачи ***нельзя*** пользоваться массивами и прочими динамическими структурами данных. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "x = (0 для завершения) 1\n",
      "x = (0 для завершения) 2\n",
      "x = (0 для завершения) 0\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "def reverse():\n",
    "    x = int(input(\"x = (0 для завершения)\"))\n",
    "    if x!=0:\n",
    "        reverse()\n",
    "    print(x)\n",
    "\n",
    "reverse()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ханойские башни\n",
    "\n",
    "<img src=\"hanoi.jpg\" width=\"50%\" align = left style=\"padding-right: 20px\">\n",
    "    \n",
    "**Оригинальная головоломка**. Даны три стержня, на один из которых нанизаны восемь колец, причём кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов на другой стержень. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее. \n",
    "\n",
    "**Легенда**. В Великом храме города Бенарес, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времён, монахи этого монастыря провинились перед богом Брахмой. Разгневанный Брахма воздвиг три высоких стержня и на один из них возложил 64 диска, сделанных из чистого золота. Причём так, что каждый меньший диск лежит на большем. \n",
    "Как только все 64 диска будут переложены со стержня, на который Брахма сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир. \n",
    "\n",
    "Источник информации: <a href=\"https://ru.wikipedia.org/wiki/%D0%A5%D0%B0%D0%BD%D0%BE%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D0%B1%D0%B0%D1%88%D0%BD%D1%8F\">статья в Википедии</a>.\n",
    "    \n",
    "<a href=\"towers.swf\">Демонстрация</a>\n",
    "\n",
    "**Задача**. Разработать программу, перемещающую диски с левого стержня на правый по указанному правилу.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 ==> 3\n",
      "1 ==> 2\n",
      "3 ==> 2\n",
      "1 ==> 3\n",
      "2 ==> 1\n",
      "2 ==> 3\n",
      "1 ==> 3\n"
     ]
    }
   ],
   "source": [
    "# текст программы\n",
    "def move(n, start, end, empty):\n",
    "    if n>0:\n",
    "        move(n-1, start, empty, end)\n",
    "        print(f'{start} ==> {end}')\n",
    "        move(n-1, empty, end, start)\n",
    "\n",
    "move(3, start=1, end=3, empty=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "584542046090.0"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(2**64-1)//60//60//24//365.25"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"https://staticlb.rmr.rocks/uploads/pics/02/55/818.jpg\" align=\"left\" width=\"140\">\n",
    "\n",
    "**Идея использована в рассказе:**\n",
    "Артур Кларк. [Девять миллиардов имён Бога.](https://librebook.me/the_nine_billion_names_of_god/vol1/1) \n",
    " \n",
    "***Чтобы хорошо сдать экзамен, лучше бы прочитать!***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Визуализация рекурсии (для самостоятельной работы)\n",
    "\n",
    "Источник: http://aliev.me/runestone/Recursion/intro-VisualizingRecursion.html\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Черепашья графика**.\n",
    "\n",
    "http://acm.mipt.ru/twiki/bin/view/Cintro/PythonTurtleInfo (кратко, на русском)\n",
    "\n",
    "https://docs.python.org/3/library/turtle.html (подробная документация, на английском)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# программа откроется в отдельном окне\n",
    "from turtle import *\n",
    "color('red', 'yellow')\n",
    "begin_fill()\n",
    "while True:\n",
    "    forward(200)\n",
    "    left(170)\n",
    "    if abs(pos()) < 1:\n",
    "        break\n",
    "end_fill()\n",
    "done()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Подключение (упрощенной) черепашьей графики для jupyter notebook**\n",
    "\n",
    "Выполнить в командной строке (Windows PowerShell)\n",
    "```\n",
    "pip install ipyturtle\n",
    "jupyter nbextension enable --py --sys-prefix ipyturtle\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Основные команды управления черепашкой:\n",
    "\n",
    "```python\n",
    "back(length)\n",
    "forward(length)\n",
    "left(degree)\n",
    "right(degree)\n",
    "pendown()\n",
    "penup()\n",
    "pencolor(r, g, b)\n",
    "showturtle()\n",
    "hideturtle()\n",
    "reset()\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Инициализация окна рисования**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ipyturtle import Turtle\n",
    "my_t = Turtle(fixed=False)\n",
    "my_t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sys.setrecursionlimit(1000)\n",
    "# рекурсивное рисование спирали\n",
    "def draw_spiral(t, line_len):\n",
    "        if line_len > 0:\n",
    "            t.forward(line_len)\n",
    "            t.right(90)\n",
    "            draw_spiral(t,line_len-3)\n",
    "    \n",
    "# холст в исходном положении\n",
    "my_t.reset()\n",
    "# опускаем черепашку в левый нижний угол\n",
    "my_t.penup()\n",
    "my_t.back(150)\n",
    "my_t.left(90)\n",
    "my_t.forward(150)\n",
    "my_t.right(90)\n",
    "my_t.pendown()\n",
    "# рисуем спираль\n",
    "draw_spiral(my_t,300)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# рекурсивное рисование дерева\n",
    "def tree(branch_len,t):\n",
    "    t.pencolor(r=4*branch_len, g=255-3*branch_len, b = 2*branch_len)\n",
    "    t.pendown()\n",
    "    if branch_len > 5:\n",
    "        t.forward(branch_len)\n",
    "        t.right(20)\n",
    "        tree(branch_len-7,t)\n",
    "        t.left(40)\n",
    "        tree(branch_len-7,t)\n",
    "        t.right(20)\n",
    "        t.penup()\n",
    "        t.back(branch_len)\n",
    "\n",
    "# холст в исходном положении\n",
    "my_t.reset()\n",
    "# опускаем черепашку вниз\n",
    "my_t.penup()\n",
    "my_t.back(100)\n",
    "my_t.pendown()\n",
    "# рисуем дерево\n",
    "tree(50,my_t)\n",
    "my_t.hideturtle()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Вместо послесловия\n",
    "\n",
    "\n",
    ">**12.1.1 Why Functions?**\n",
    ">\n",
    ">There is a long and disreputable tradition of writing very long functions – hundreds of lines long. I once encountered a single (handwritten) function with more than 32,768 lines of code. Writers of such functions seem to fail to appreciate one of the primary purposes of functions: to break up complicated computations into meaningful chunks and name them. We want our code to be comprehensible, because that is the first step on the way to maintainability. The first step to comprehensibility is to break computational tasks into comprehensible chunks (represented as functions and classes) and name those. Such functions then provide the basic vocabulary of computation, just as the types (built-in and user-defined) provide the basic vocabulary of data. ... \n",
    "Next, we can compose functions representing common or specialized tasks into larger computations. \n",
    ">\n",
    ">The number of errors in code correlates strongly with the amount of code and the complexity of the code. Both problems can be addressed by using more and shorter functions. Using a function to do a specific task often saves us from writing a specific piece of code in the middle of other code; making it a function forces us to name the activity and document its dependencies. Also, function\n",
    "call and return saves us from using error-prone control structures... \n",
    ">\n",
    ">The most basic advice is to keep a function of a size so that you can look at it in total on a screen. Bugs tend to creep in when we can view only part of an algorithm at a time. For many programmers that puts a limit of about 40 lines on a function. My ideal is a much smaller size still, maybe an average of 7 lines. \n",
    ">\n",
    ">In essentially all cases, the cost of a function call is not a significant factor ... Use functions as a structuring mechanism.\n",
    "\n",
    "<div align=right>\n",
    "    Bjarne Stroustrup. The C++ Programming Language. Fourth Edition. Addison-Wesley, 2013."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "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.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}