python_recursion.ipynb

{
  "cells": [
    {
      "cell_type": "markdown",
      "id": "7384ed77",
      "metadata": {},
      "source": [
        "<img src=\"https://raw.githubusercontent.com/dark-teal-coder/dark-teal-coder/main/images/coder-no-background-000-128-128.png\" alt=\"coder-black-background-000-128-128.png\" width=\"100\" height=\"100\" align=\"right\" style=\"margin:0px 5%; padding: 5px;\">\n",
        "<p>\n",
        "\tGitHub: <a href=\"https://github.com/dark-teal-coder\">@dark-teal-coder</a>\n",
        "\t<br />\n",
        "\tFirst Published Date: 2022-03-23\n",
        "\t<br />\n",
        "\tLast Modified Date: 2022-05-10\n",
        "</p>\n",
        "\n",
        "<br />\n",
        "\n",
        "___"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "da06c10f",
      "metadata": {
        "id": "da06c10f"
      },
      "source": [
        "# Defining Recursion "
      ]
    },
    {
      "cell_type": "markdown",
      "id": "f49b9e90",
      "metadata": {
        "id": "f49b9e90"
      },
      "source": [
        "> *Definition*: Recursion is the repeated application of the same procedure to a smaller problem."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "4d329e3a",
      "metadata": {
        "id": "4d329e3a"
      },
      "source": [
        "In programming, recursion is a way of doing a repetitive task by having a function call itself with a modified parameter until it reaches a specific condition. This condition is called base case. \n",
        "\n",
        "A recursive function must include a recursive case and base case. The recursive case calls the function again, with a different value. The base case returns a value without calling the same function."
      ]
    },
    {
      "cell_type": "markdown",
      "id": "0fda6afe",
      "metadata": {
        "id": "0fda6afe"
      },
      "source": [
        "Recursive Function Structure: \n",
        "\n",
        "```\n",
        "def recursive_function(parameters):\n",
        "    if base_case_condition(parameters):\n",
        "        return base_case_value\n",
        "    recursive_function(modified_parameters)\n",
        "```"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "80d60f7d",
      "metadata": {
        "id": "80d60f7d"
      },
      "source": [
        "# Examples of Recursions in Python"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "03000794",
      "metadata": {
        "id": "03000794"
      },
      "outputs": [],
      "source": [
        "def sum_positive_integers(num):\n",
        "\t'''This function uses recursion to sum all the positive numbers of the input number at parameter 1.'''\n",
        "\tif num < 1:\n",
        "\t\treturn 0\n",
        "\t## The recursive case is adding this number to the sum of the numbers smaller than this one.\n",
        "\treturn num + sum_positive_integers(num - 1)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "d9ada29d",
      "metadata": {
        "id": "d9ada29d",
        "outputId": "cec899a4-d0f1-4f59-d5ea-e728af29d7bd"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "6\n",
            "15\n"
          ]
        }
      ],
      "source": [
        "print(sum_positive_integers(3)) # Output: 6\n",
        "print(sum_positive_integers(5)) # Output: 15"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "d56b89bf",
      "metadata": {
        "id": "d56b89bf"
      },
      "outputs": [],
      "source": [
        "def factorial(num): \n",
        "\tprint(f\"Factorial called with {str(num)}\")\n",
        "\tif num < 2: \n",
        "\t\tprint(\"Returning 1\")\n",
        "\t\treturn 1\n",
        "\tresult = num * factorial(num - 1)\n",
        "\tprint(f\"Returning {str(result)} for factorial of {str(num)}\")\n",
        "\treturn result"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "70cd5989",
      "metadata": {
        "id": "70cd5989",
        "outputId": "1f2bd79c-2d6a-486a-c63f-8675a973bf3d"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Factorial called with 5\n",
            "Factorial called with 4\n",
            "Factorial called with 3\n",
            "Factorial called with 2\n",
            "Factorial called with 1\n",
            "Returning 1\n",
            "Returning 2 for factorial of 2\n",
            "Returning 6 for factorial of 3\n",
            "Returning 24 for factorial of 4\n",
            "Returning 120 for factorial of 5\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "120"
            ]
          },
          "execution_count": 4,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "factorial(5)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "2fab6a4a",
      "metadata": {
        "id": "2fab6a4a"
      },
      "outputs": [],
      "source": [
        "def is_power_of(number, base):\n",
        "\t# Base case: when number is smaller than base.\n",
        "\tif number < base:\n",
        "\t\t# If number is equal to 1, it's a power (base**0).\n",
        "\t\t\tif number == 1: \n",
        "\t\t\t\treturn True \n",
        "\t\t\telse: \n",
        "\t\t\t\treturn False\n",
        "\t# Recursive case: keep dividing number by base.\n",
        "\treturn is_power_of(number/base, base)\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "4b8d59f1",
      "metadata": {
        "id": "4b8d59f1",
        "outputId": "bb2dd269-d744-4fcd-dab7-7f15d97a3660"
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "True\n",
            "True\n",
            "False\n"
          ]
        }
      ],
      "source": [
        "print(is_power_of(8,2)) # Output: True\n",
        "print(is_power_of(64,4)) # Output: True\n",
        "print(is_power_of(70,10)) # Output: False"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "f3b663b7",
      "metadata": {
        "id": "f3b663b7"
      },
      "source": [
        "## When to Use Recursion"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "d6c796da",
      "metadata": {
        "id": "d6c796da"
      },
      "source": [
        "We can use loops to do the tasks recursion does but it will be easier to write and understand recursive functions in some cases. Many mathematical functions are already defined in recursive terms so it is more intuitive to write the code as a recursive function. It is also useful in IT contexts as well. For example, if we want to go through directories and calculate the number of files contained in each. When listing the files inside a directory, we may find sub-directories inside them and want to count the files inside those sub-directories inside them as well. This is a great time to use recursion. The base case would be a directory with no sub-directories. The function will simply return the amount of files inside it. The recursive case would be calling the recursive function for each of the contained sub-directories. The function will return the sum of all files in that directory and of all files in the contained sub-directories. "
      ]
    },
    {
      "cell_type": "markdown",
      "id": "cd995c4a",
      "metadata": {
        "id": "cd995c4a"
      },
      "source": [
        "## Limitation"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "155d98e2",
      "metadata": {
        "id": "155d98e2"
      },
      "source": [
        "In Python, there is a maximun recursion depth. If we use recursion over it, we will receive a ```RecursionError```. According to [Python's Built-in Exceptions Documentation](https://docs.python.org/3/library/exceptions.html), we can use ```getrecursionlimit()``` to find the maximum recursion depth. See below. \n",
        "\n",
        "```python\n",
        "import sys\n",
        "sys.getrecursionlimit()\n",
        "```"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "name": "example_recursion.ipynb",
      "provenance": []
    },
    "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.8.12"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}