005_Python_Function_Recursion.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<small><small><i>\n",
    "All the IPython Notebooks in **Python Functions** lecture series by Dr. Milaan Parmar are available @ **[GitHub](https://github.com/milaan9/04_Python_Functions)**\n",
    "</i></small></small>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python Recursion\n",
    "\n",
    "In this class, you will learn to create a recursive function (a function that calls itself again and again)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What is recursion?\n",
    "\n",
    "Recursion is the process of defining something in terms of itself.\n",
    "\n",
    "A physical world example would be to **place two parallel mirrors facing each other**. Any object in between them would be reflected recursively."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python Recursive Function\n",
    "\n",
    "In Python, we know that a **[function](https://github.com/milaan9/04_Python_Functions/blob/main/001_Python_Functions.ipynb)** can call other functions. It is even possible for the function to call itself. These types of construct are termed as recursive functions.\n",
    "\n",
    "The following image shows the working of a recursive function called **`recurse`**.\n",
    "\n",
    "<div>\n",
    "<img src=\"img/re1.png\" width=\"250\"/>\n",
    "</div>\n",
    "\n",
    "Following is an example of a recursive function to find the factorial of an integer.\n",
    "\n",
    "Factorial of a number is the product of all the integers from 1 to that number. For example, the factorial of 6 (denoted as 6!) is \n",
    "\n",
    "```python\n",
    "1*2*3*4*5*6 = 720.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-06-13T16:03:47.995819Z",
     "start_time": "2021-06-13T16:03:47.984100Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The factorial of 3 is 6\n"
     ]
    }
   ],
   "source": [
    "# Example 1:\n",
    "\n",
    "def factorial(n):\n",
    "    \"\"\"This is a recursive function to find the factorial of an integer\"\"\"\n",
    "\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return (n * factorial(n-1))  # 3 * 2 * 1 = 6\n",
    "\n",
    "\n",
    "num = 3\n",
    "print(\"The factorial of\", num, \"is\", factorial(num))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the above example, **`factorial()`** is a recursive function as it calls itself."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When we call this function with a positive integer, it will recursively call itself by decreasing the number.\n",
    "\n",
    "Each function multiplies the number with the factorial of the number below it until it is equal to one. This recursive call can be explained in the following steps.\n",
    "\n",
    "```python\n",
    "factorial(3)          # 1st call with 3\n",
    "3 * factorial(2)      # 2nd call with 2\n",
    "3 * 2 * factorial(1)  # 3rd call with 1\n",
    "3 * 2 * 1             # return from 3rd call as number=1\n",
    "3 * 2                 # return from 2nd call\n",
    "6                     # return from 1st call\n",
    "```\n",
    "\n",
    "Let's look at an image that shows a step-by-step process of what is going on:\n",
    "\n",
    "<div>\n",
    "<img src=\"img/re2.png\" width=\"350\"/>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our recursion ends when the number reduces to 1. This is called the base condition.\n",
    "\n",
    "Every recursive function must have a base condition that stops the recursion or else the function calls itself infinitely.\n",
    "\n",
    "The Python interpreter limits the depths of recursion to help avoid infinite recursions, resulting in stack overflows.\n",
    "\n",
    "By default, the maximum depth of recursion is **`1000`**. If the limit is crossed, it results in **`RecursionError`**. Let's look at one such condition."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2021-06-13T16:04:11.723151Z",
     "start_time": "2021-06-13T16:04:05.119692Z"
    }
   },
   "outputs": [
    {
     "ename": "RecursionError",
     "evalue": "maximum recursion depth exceeded",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mRecursionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-2-3ec8c6652eef>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mrecursor\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      2\u001b[0m     \u001b[0mrecursor\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 3\u001b[1;33m \u001b[0mrecursor\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-2-3ec8c6652eef>\u001b[0m in \u001b[0;36mrecursor\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mrecursor\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m     \u001b[0mrecursor\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m \u001b[0mrecursor\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "... last 1 frames repeated, from the frame below ...\n",
      "\u001b[1;32m<ipython-input-2-3ec8c6652eef>\u001b[0m in \u001b[0;36mrecursor\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mrecursor\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m     \u001b[0mrecursor\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m \u001b[0mrecursor\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mRecursionError\u001b[0m: maximum recursion depth exceeded"
     ]
    }
   ],
   "source": [
    "def recursor():\n",
    "    recursor()\n",
    "recursor()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Advantages of Recursion\n",
    "\n",
    "1. Recursive functions make the code look clean and elegant.\n",
    "2. A complex task can be broken down into simpler sub-problems using recursion.\n",
    "3. Sequence generation is easier with recursion than using some nested iteration."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Disadvantages of Recursion\n",
    "\n",
    "1. Sometimes the logic behind recursion is hard to follow through.\n",
    "2. Recursive calls are expensive (inefficient) as they take up a lot of memory and time.\n",
    "3. Recursive functions are hard to debug."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "hide_input": false,
  "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"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}