{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recursion practice problems"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Print the nth fibonacci term using recursion.\n",
    "def fibonacci(n):\n",
    "    \"\"\"\n",
    "    returns the nth value of the fibonacci series\n",
    "    \"\"\"\n",
    "    assert int(n) == n and n >= 0, \"The number must belong to the set of whole numbers\"\n",
    "    if n in (0, 1):\n",
    "        return n\n",
    "    else:\n",
    "        return fibonacci(n - 1) + fibonacci(n - 2)\n",
    "\n",
    "fibonacci(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the factorial of a number using recursion.\n",
    "def factorial(number):\n",
    "    \"\"\"\n",
    "    Calculates the factorial of a number using recursion.\n",
    "    \"\"\"\n",
    "    assert int(number) == number and number >= 0, \"The number must be a whole number\"\n",
    "\n",
    "    if number in (0, 1):\n",
    "        return 1\n",
    "    else:\n",
    "        return number * factorial(number - 1)\n",
    "\n",
    "factorial(5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Element found at position 3\n"
     ]
    }
   ],
   "source": [
    "# Perform binary search using recursion.\n",
    "def binarySearch(array, low, high, target):\n",
    "    \"\"\"\n",
    "    Performs a binary search operation in the given array.\n",
    "    \"\"\"\n",
    "    mid = int((low + high) / 2)\n",
    "    if array[mid] == target:\n",
    "        return f\"Element found at position {mid}\"\n",
    "    elif array[mid] > target:\n",
    "        high = mid - 1\n",
    "        return binarySearch(array, low, high, target)\n",
    "    elif array[mid] < target:\n",
    "        low = mid + 1\n",
    "        return binarySearch(array, low, high, target)\n",
    "    else:\n",
    "        return \"Element not found\"\n",
    "\n",
    "# Driver Code\n",
    "if __name__ == \"__main__\":\n",
    "    arr = [2, 3, 4, 5, 6, 7]\n",
    "    low = 0\n",
    "    high = len(arr) - 1\n",
    "    target = 5\n",
    "    print(binarySearch(arr, low, high, target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the sum of digits using recursion\n",
    "def number_sum(number):\n",
    "    \"\"\"\n",
    "    finds the sum of all the elements of the number.\n",
    "    \"\"\"\n",
    "    assert int(number) == number, \"Must be an integer\"\n",
    "    if number == 0:\n",
    "        return 0\n",
    "    else:\n",
    "        return number%10 + number_sum(number//10)\n",
    "\n",
    "number_sum(121)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "125"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the power of a number using recursion\n",
    "def power(number, exponent):\n",
    "    \"\"\"\n",
    "    calculates the positive power of a number.\n",
    "    \"\"\"\n",
    "    if exponent == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return number * power(number, exponent - 1)\n",
    "\n",
    "power(5, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the GCD of two numbers using recursion\n",
    "def gcd(num_1, num_2):\n",
    "    \"\"\"\n",
    "    calculated the gcd of two numbers\n",
    "    \"\"\"\n",
    "    if num_1 == num_2:\n",
    "        return num_1\n",
    "    \n",
    "    elif num_1 > num_2:\n",
    "        num_1 -= num_2\n",
    "        return gcd(num_1, num_2)\n",
    "    else:\n",
    "        num_2 -= num_1\n",
    "        return gcd(num_1, num_2)\n",
    "\n",
    "gcd(50, 25)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Convert a number into binary format using recursion\n",
    "def binary(number):\n",
    "    \"\"\"\n",
    "    converts a number into binary format\n",
    "    \"\"\"\n",
    "    assert int(number) == number, \"The number must be an integer\"\n",
    "\n",
    "    if number == 0:\n",
    "        return number\n",
    "    else:\n",
    "        return number%2 + 10*binary(number//2)\n",
    "\n",
    "binary(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "40d3a090f54c6569ab1632332b64b2c03c39dcf918b08424e98f38b5ae0af88f"
  },
  "kernelspec": {
   "display_name": "Python 3.8.3 ('base')",
   "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.3"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}