TailRecursionPractice.ipynb

tailrecursionpractice.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyM0XLHbK+dc01W+bq/R8UNZ",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/gist/heathhenley/681e9f7c67ce51ff61b712c467a8dcf8/tailrecursionpractice.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "hLijdqIkc25P"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "id": "T_WSJR8_SeBp"
      },
      "outputs": [],
      "source": [
        "def list_len(lst: list) -> int:\n",
        "    if not lst:\n",
        "        return 0\n",
        "    return 1 + list_len(lst[1:])\n",
        "\n",
        "# Exploding stack\n",
        "# --> 1 + len([2, 3, 4, 5, 6])\n",
        "# --> 1 + (1  + len([3, 4, 5, 6]))\n",
        "# --> 1 + (1 + (1 + len([4, 5, 6])))\n",
        "# --> 1 + (1 + (1 + (1 + len([5, 6]))))\n",
        "# --> 1 + (1 + (1 + (1 + (1 + len([6])))))\n",
        "# --> 1 + (1 + (1 + (1 + (1 + (1))))\n",
        "# --> # --> 1 + (1 + (1 + (1 + 2)))\n",
        "# --> 1 + (1 + (1 + 3))\n",
        "# --> 1 + (1 + 4)\n",
        "# --> 1 + 5\n",
        "# --> 6\n",
        "\n",
        "def list_len_tail_rec(lst: list, acc: int = 0) -> int:\n",
        "    if not lst:\n",
        "        return acc\n",
        "    return list_len_tail_rec(lst[1:], acc + 1)\n",
        "\n",
        "assert list_len_tail_rec([1, 2, 3, 4, 5, 6]) == list_len([1, 2, 3, 4, 5, 6])\n",
        "\n",
        "\n",
        "# Constant stack size\n",
        "# --> len([2, 3, 4, 5, 6], 1)\n",
        "# --> len([3, 4, 5, 6], 2)\n",
        "# --> len([4, 5, 6], 3)\n",
        "# --> len([5, 6], 4)\n",
        "# --> len([6], 5)\n",
        "# --> len([], 6)\n",
        "# --> 6\n",
        "\n",
        "\n",
        "def list_sum(lst: list) -> int:\n",
        "    match lst:\n",
        "        case []:\n",
        "            return 0\n",
        "        case [head, *tail]:\n",
        "            return head + list_sum(tail)\n",
        "\n",
        "# Exploding stack\n",
        "# --> 1 + sum([2, 3, 4, 5, 6])\n",
        "# --> 1 + (2 + sum([3, 4, 5, 6]))\n",
        "# --> 1 + (2 + (3 + sum([4, 5, 6])))\n",
        "# --> 1 + (2 + (3 + (4 + sum([5, 6]))))\n",
        "# --> 1 + (2 + (3 + (4 + (5 + sum([6])))))\n",
        "# --> 1 + (2 + (3 + (4 + (5 + (6 + 0))))))\n",
        "# --> 1 + (2 + (3 + (4 + (5 + (6))))))\n",
        "# --> 1 + (2 + (3 + (4 + (11))))\n",
        "# --> 1 + (2 + (3 + (15)))\n",
        "# --> 1 + (2 + (18))\n",
        "# --> 1 + (20)\n",
        "# --> 21\n",
        "\n",
        "def list_sum_tail_rec(lst: list, acc: int = 0) -> int:\n",
        "    match lst:\n",
        "        case []:\n",
        "            return acc\n",
        "        case [head, *tail]:\n",
        "            return list_sum_tail_rec(tail, acc + head)\n",
        "\n",
        "# Constant stack size\n",
        "# --> sum([2, 3, 4, 5, 6], 0 + 1)\n",
        "# --> sum([3, 4, 5, 6], 1 + 2)\n",
        "# --> sum([4, 5, 6], 3 + 3)\n",
        "# --> sum([5, 6], 6 + 4)\n",
        "# --> sum([6], 10 + 5)\n",
        "# --> sum([], 15 + 6)\n",
        "# --> 21\n",
        "\n",
        "assert list_sum_tail_rec([1, 2, 3, 4, 5, 6]) == list_sum([1, 2, 3, 4, 5, 6])\n",
        "\n",
        "\n",
        "def factorial(n: int) -> int:\n",
        "    if n == 0:\n",
        "        return 1\n",
        "    return n * factorial(n - 1)\n",
        "\n",
        "# Exploding stack size\n",
        "# --> factorial(5)\n",
        "# --> 5 * factorial(4)\n",
        "# --> 5 * 4 * factorial(3)\n",
        "# --> 5 * 4 * 3 * factorial(2)\n",
        "# --> 5 * 4 * 3 * 2 * factorial(1)\n",
        "# --> 5 * 4 * 3 * 2 * 1 * factorial(0)\n",
        "# --> 120\n",
        "\n",
        "def factorial_tail_rec(n: int, acc: int = 1) -> int:\n",
        "    if n == 0:\n",
        "        return acc\n",
        "    return factorial_tail_rec(n - 1, acc * n)\n",
        "\n",
        "# Constant stack size\n",
        "# --> factorial(5, 1)\n",
        "# --> factorial(4, 5 * 1)\n",
        "# --> factorial(3, 5 * 4)\n",
        "# --> factorial(2, 20 * 3)\n",
        "# --> factorial(1, 60 * 2)\n",
        "# --> factorial(0, 120 * 1)\n",
        "#--> 120\n",
        "\n",
        "\n",
        "\n",
        "def fib_normal(n: int) -> int:\n",
        "    if n < 2:\n",
        "        return n\n",
        "    return fib_normal(n - 1) + fib_normal(n - 2)\n",
        "\n",
        "# Exploding stack\n",
        "# --> fib(4) + fib(3)\n",
        "# --> (fib(3) + fib(2)) + fib(3)\n",
        "# --> ((fib(2) + fib(1)) + fib(2)) + fib(3)\n",
        "# --> (((1 + 0) + fib(1)) + fib(2)) + fib(3)\n",
        "# --> ((1 + 1) + fib(2)) + fib(3)\n",
        "# --> ((2 + (1 + 0)) + fib(3)\n",
        "# --> 3 + fib(3)\n",
        "# --> 3 + (fib(2) + 1)\n",
        "# --> 3 + ((1 + 0) + 1)\n",
        "# --> 3 + (1 + 1)\n",
        "# --> 3 + 2\n",
        "# --> 5\n",
        "\n",
        "\n",
        "def fib_tail_rec(n: int, a: int = 0, b: int = 1) -> int:\n",
        "    if n == 0:\n",
        "        return a\n",
        "    return fib_tail_rec(n - 1, b, a + b)\n",
        "\n",
        "# constant stack size\n",
        "# --> fib(5, 0, 1)\n",
        "# --> fib(4, 1, 0 + 1)\n",
        "# --> fib(3, 1, 2)\n",
        "# --> fib(2, 2, 3)\n",
        "# --> fib(1, 3, 5)\n",
        "# --> fib(0, 5, 8)\n",
        "# --> 5\n",
        "\n",
        "assert fib_normal(5) == fib_tail_rec(5)"
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "XZAq5bbXSp6K"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}