2020_Python_Programming_Practical_4.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "2020 Python Programming Practical 4.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Alvarrir/2020python/blob/master/2020_Python_Programming_Practical_4.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "jp3BkDml8xiR",
        "colab_type": "text"
      },
      "source": [
        "# **2020 Python Programming Practical 4**\n",
        "\n",
        "If you do not have one already, create a [GitHub](https://github.com) account using your DHS Mail.\n",
        "\n",
        "Create a public repository 2020python\n",
        "\n",
        "File --> Save a copy in GitHub under your 2020python repository\n",
        "\n",
        "Also share this colab file with edit access with computing@dhs.sg\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "-U8w0oQW9P_b",
        "colab_type": "text"
      },
      "source": [
        "**Q1. (Summing series 1)**  \n",
        "Write a recursive function sum_series1(i) to compute the following series:   \n",
        "m(i) = 1 + ½ + ⅓ + … + 1/i\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "D0uTR7B-8qbF",
        "colab_type": "code",
        "outputId": "7fc63aa1-1e7e-4600-dae0-926bf218eaf8",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        }
      },
      "source": [
        "def sum_series(i):\n",
        "  if i <= 1: #terminating case\n",
        "    return 1\n",
        "  else: #recursive case\n",
        "    return 1/i + sum_series(i-1)\n",
        "\n",
        "#main\n",
        "print(sum_series(1)) #test terminating case\n",
        "print(sum_series(6)) #test recursive case"
      ],
      "execution_count": 74,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1\n",
            "2.4499999999999997\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7Ui5CuS_9Za1",
        "colab_type": "text"
      },
      "source": [
        "**Q2. (Summing series 2)**  \n",
        "Write a recursive function sum_series2(i) to compute the following series:   \n",
        "m(i) = ⅓ + ⅖ + 3/7 + 4/9 + 5/11 + 6/13 + … + i/(2i+1)\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CfkRAAWV9cXS",
        "colab_type": "code",
        "outputId": "1794d7ff-8661-47d4-859b-4e883ac37af2",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        }
      },
      "source": [
        "def sum_series2(i):\n",
        "  if i <= 1: #terminating case\n",
        "    return 1/3\n",
        "  else: #recursive case\n",
        "    return i/(2*i+1) + sum_series2(i-1)\n",
        "\n",
        "#main\n",
        "print(sum_series2(1)) #test terminating case\n",
        "print(sum_series2(6)) #test recursive case"
      ],
      "execution_count": 73,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0.3333333333333333\n",
            "2.5224331224331227\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aVhHiT8w9c7d",
        "colab_type": "text"
      },
      "source": [
        "**Q3. (Computing GCD)**  \n",
        "The greatest common divisor (GCD) of two positive integers m and n, gcd(m, n) can be defined recursively as follows:  \n",
        "\n",
        "If m % n is 0, gcd(m, n) is n.  \n",
        "Otherwise, gcd(m, n) is gcd(n, m % n).  \n",
        "\n",
        "Write a recursive function gcd(m, n) to find the GCD. Write a test program that computes gcd(24, 16) and gcd(255, 25)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PwRmweEa9fny",
        "colab_type": "code",
        "outputId": "46663fc6-d6a5-4245-f488-0ce2fe9f9d90",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 67
        }
      },
      "source": [
        "def gcd(m, n):\n",
        "  if m % n == 0: # terminating case\n",
        "    return n\n",
        "  else: # recursive case\n",
        "    return gcd(n, m%n)\n",
        "\n",
        "# main\n",
        "print(gcd(24, 24)) #test terminating case\n",
        "print(gcd(24, 16)) #test recursive case\n",
        "print(gcd(255, 25))"
      ],
      "execution_count": 71,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "24\n",
            "8\n",
            "5\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "wWe4kRS8ZmwP"
      },
      "source": [
        "**Q4. (Reverse the digits in an integer)**  \n",
        "Write a recursive function reverse_int(n) that reverses the digits of an integer n: \n",
        "\n",
        "For example, reverse_int(12345) displays 54321."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aOozTwoR9j9B",
        "colab_type": "code",
        "outputId": "900b5f33-81ff-42c1-c0ff-8578bdab3707",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        }
      },
      "source": [
        "def reverse_int(n):\n",
        "  if n < 10: # termianting case: single digit\n",
        "    return n\n",
        "  else: # recursive case: place last digit infront, update remainding\n",
        "    return int(str(n % 10) + str(reverse_int(n // 10)))\n",
        "\n",
        "# main\n",
        "print(reverse_int(8)) # test terminating case\n",
        "print(reverse_int(12345)) # test recursive case"
      ],
      "execution_count": 70,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "8\n",
            "54321\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "lE0ScX9e9kcg",
        "colab_type": "text"
      },
      "source": [
        "**Q5. (Occurrences of a specified character in a string)**  \n",
        "Write a recursive function count_letter(str, ch) that finds the number of occurrences of a specified letter ch in a string str: \n",
        "\n",
        "For example, count_letter(\"Welcome\", 'e') returns 2."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sE_bxwDs9mf6",
        "colab_type": "code",
        "outputId": "872d3608-7c00-4659-8aad-d98866f3d6fb",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 67
        }
      },
      "source": [
        "def count_letter(strg,ch):\n",
        "  if len(strg) == 0: #terminating case\n",
        "    return 0\n",
        "  else:\n",
        "    if strg[0] != ch: #recursive case 1: if ch not in strg\n",
        "      return count_letter(strg[1:], ch)\n",
        "    else: #recursive case 2: if ch in strg\n",
        "      return 1 + count_letter(strg[1:], ch)\n",
        "\n",
        "#main\n",
        "print(count_letter(\"\",\"\")) #test terminating case\n",
        "print(count_letter(\"Hello\",\"c\")) #test recursive case 1 + 2\n",
        "print(count_letter(\"Welcome\",\"e\")) #test recursive case 2"
      ],
      "execution_count": 69,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0\n",
            "0\n",
            "2\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "KSviQY0T9m7Q",
        "colab_type": "text"
      },
      "source": [
        "**Q6. (Summing the digits in an integer)**  \n",
        "Write a recursive function sum_digits(n) that computes the sum of the digits in an integer n: \n",
        "\n",
        "For example, sum_digits(234) returns 9."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "YbH9Pbul9rK-",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 50
        },
        "outputId": "d14219ab-ea5c-4d84-84d6-c106e2535b28"
      },
      "source": [
        "def sum_digits(n):\n",
        "  if n < 10: #terminating case\n",
        "    return n\n",
        "  else: #recursive case\n",
        "    return n % 10 + sum_digits(n//10)\n",
        "\n",
        "#main\n",
        "print(sum_digits(9)) #test terminating case\n",
        "print(sum_digits(234)) #test recursive case"
      ],
      "execution_count": 68,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "9\n",
            "9\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "V9Z95nlg97e4",
        "colab_type": "text"
      },
      "source": [
        "**Q7. (Finding the largest number in an array)**  \n",
        "Write a recursive function find_largest(alist) that returns the largest integer in an array alist.  \n",
        "\n",
        "For example, given alist = [5, 1, 8, 7, 2], sum_digits(alist) returns 8.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "1AZvvAW499PK",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 84
        },
        "outputId": "6fcfee0c-ae1d-4f1b-d7d7-df06107b1bc4"
      },
      "source": [
        "def find_largest(alist):\n",
        "    if len(alist) == 1: #terminating case\n",
        "        return alist[0]\n",
        "    else:\n",
        "        if find_largest(alist[1:]) < alist[0]: #recursive case 1: if number checked is not bigger than previous, return previous\n",
        "          return alist[0]\n",
        "        else: #recursive case 2: if number checked is bigger than previous, update it as \"previous\"\n",
        "          return find_largest(alist[1:])\n",
        "\n",
        "#main\n",
        "print(find_largest([1])) #test terminating case\n",
        "print(find_largest([5, 1, 8, 7, 2])) #test recursive case 1 + 2\n",
        "print(find_largest([6, 1, 1, 1, 1, 1])) #test recursive case 1 + 2 where largest is alist[first]\n",
        "print(find_largest([1, 1, 1, 1, 1, 6])) #test recursive case 1 + 2 where largest is alist[last]"
      ],
      "execution_count": 67,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1\n",
            "8\n",
            "6\n",
            "6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "KNHIvXFleFFH"
      },
      "source": [
        "**Q8. (Finding the number of uppercase letters in a string)**  \n",
        "Write a recursive function find_num_uppercase(str) to return the number of uppercase letters in a string str.\n",
        "\n",
        "For example, find_num_uppercase('Good MorninG!') returns 3.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-CZ0M7j6eHQe",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 67
        },
        "outputId": "1821f360-afb5-4d87-d879-28ff3de5f675"
      },
      "source": [
        "def find_num_uppercase(strings):\n",
        "  if len(strings) == 0: #terminating case\n",
        "    return 0\n",
        "  else:\n",
        "    if (strings[0]).isupper() == False: #recursive case 1: if letter not capitalised, check next\n",
        "      return find_num_uppercase(strings[1:])\n",
        "    else: #recursive case 2: if lettr is capitalised, update and check next\n",
        "      return 1 + find_num_uppercase(strings[1:])\n",
        "\n",
        "#main\n",
        "print(find_num_uppercase(\"\")) #test terminating case\n",
        "print(find_num_uppercase(\"Good MorninG\")) #test recursive case\n",
        "print(find_num_uppercase(\" 'I'm coming to help. Where are you? I can't see you. I. Can't. See you.' ~ Fiddlesticks\")) #test recursive case with added fluff"
      ],
      "execution_count": 66,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0\n",
            "3\n",
            "7\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "bRZi88-5BxHK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}