{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Рекурсия"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recur2.** Описать рекурсивную функцию `fact2(n)` вещественного типа, вычисляющую значение двойного факториала\n",
    "\n",
    "N!! = N·(N−2)·(N−4)·…\n",
    "\n",
    "(N > 0 — параметр целого типа; последний сомножитель в произведении равен 2, если N — четное число, и 1, если N — нечетное). С помощью этой функции вычислить двойные факториалы пяти данных чисел."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#описание функции\n",
    "def fact2(n):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#основная программа\n",
    "..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#тестирование функции\n",
    "assert fact2(1)==1, \"Test 1\"\n",
    "assert fact2(5)==15, \"Test 2\"\n",
    "assert fact2(6)==48, \"Test 3\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recur3.** Описать рекурсивную функцию `power_n(x, n)` вещественного типа, находящую значение n-й степени числа x по формулам:\n",
    "\n",
    "$x^0 = 1,$\n",
    "\n",
    "$x^n = (x^{n/2})^2$ при четных $n > 0,$\n",
    "\n",
    "$x^n = x*x^{n-1}$ при нечетных $n > 0,$\n",
    "\n",
    "$x^n = 1/x^{-n}$ при  $n < 0$\n",
    "\n",
    "(x ≠ 0 — вещественное число, n — целое; в формуле для четных n должна использоваться операция целочисленного деления). С помощью этой функции найти значения $x^n$ для данного x при пяти данных значениях n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#описание функции\n",
    "def power_n(x, n):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#основная программа\n",
    "..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#тестирование функции\n",
    "assert power_n(2, 5)==32.0, \"Test 1\"\n",
    "assert power_n(2, -2)==0.25, \"Test 2\"\n",
    "assert power_n(3, 2)==9.0, \"Test 3\"\n",
    "assert power_n(0.5, -2)==4.0, \"Test 4\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recur4.** Описать рекурсивную функцию `fib1(N)` целого типа, вычисляющую N-й элемент последовательности чисел Фибоначчи (N — целое число):\n",
    "\n",
    "$F_1 = F_2 = 1,        F_K = F_{K−2} + F_{K−1},    K = 3, 4, … .$\n",
    "\n",
    "С помощью этой функции найти пять чисел Фибоначчи с данными номерами, и вывести эти числа вместе с количеством рекурсивных вызовов функции fib1, потребовавшихся для их нахождения."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#описание функции\n",
    "def fib1(N):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#основная программа\n",
    "..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#тестирование функции\n",
    "assert fib1(2)==1, \"Test 1\"\n",
    "assert fib1(6)==8, \"Test 2\"\n",
    "#количество рекурсивных вызовов необходимо искать с помощью глобальной переменной. \n",
    "#Тестовые значения необходимо определить самостоятельно, \"пройдя\" рекурсивный алгоритм для n=4,5,6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recur8.** Описать рекурсивную функцию `root_k(x, k, n)` вещественного типа, находящую приближенное значение корня k-й степени из числа x по формуле:\n",
    "\n",
    "$y_0 = 1,        y_{n+1} = y_n − (y_n − x/(y_n)^{k−1})/k,$\n",
    "\n",
    "где $y_n$ обозначает root_k(x, k, n) при фиксированных $x$ и $k$. Параметры функции: $x$ (> 0) — вещественное число, $k$ (>1) и $n$ (>0) — целые. С помощью функции root_k найти для данного числа $x$ приближенные значения его корня $k$-й степени при шести данных значениях $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#описание функции\n",
    "def root_k(x, k, n):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#основная программа\n",
    "..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#тестирование функции\n",
    "assert root_k(0.5, 2, 2)-0.708333333<1e-9, \"Test 1\"\n",
    "assert root_k(0.5, 2, 4)-0.70710678<1e-8, \"Test 2\"\n",
    "assert root_k(9, 2, 3)-3.02352941<1e-8, \"Test 3\"\n",
    "assert root_k(9, 2, 6)-3.0<1e-10, \"Test 4\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recur9.** Описать рекурсивную функцию `gcd(a, b)` целого типа, находящую наибольший общий делитель (НОД, greatest common divisor) двух целых положительных чисел a и b, используя алгоритм Евклида:\n",
    "\n",
    "НОД(A, B) = НОД(B, A mod B),    B ≠ 0;        НОД(A, 0) = A,\n",
    "\n",
    "где «mod» обозначает операцию взятия остатка от деления. С помощью этой функции найти НОД(A, B), НОД(A, C), НОД(A, D), если даны числа A, B, C, D."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#описание функции\n",
    "def gcd(a,b):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#основная программа\n",
    "..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#тестирование функции\n",
    "assert gcd(15,5)==5,\"Test 1\"\n",
    "assert gcd(24,18)==6,\"Test 2\"\n",
    "assert gcd(15,13)==1,\"Test 3\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recur10.** Описать рекурсивную функцию `digit_sum(k)` целого типа, которая находит сумму цифр целого числа k, не используя оператор цикла. С помощью этой функции найти суммы цифр для пяти данных целых чисел."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#описание функции\n",
    "def digit_sum(k):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#основная программа\n",
    "..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#тестирование функции\n",
    "assert digit_sum(5)==5,\"Test 1\"\n",
    "assert digit_sum(125)==8,\"Test 2\"\n",
    "assert digit_sum(10001)==2,\"Test 3\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Последняя задача.**\n",
    "Вычислить количество единиц в двоичной записи целого неотрицательного числа. С помощью этой функции найти количество единиц для пяти данных целых чисел."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#описание функции\n",
    "def count_entities(k):\n",
    "    ..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#основная программа\n",
    "..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#тестирование функции\n",
    "assert count_entities(5)==2,\"Test 1\"\n",
    "assert count_entities(0)==0,\"Test 2\"\n",
    "assert count_entities(8)==1,\"Test 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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}