Recursion_Practice_Problems.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "h38Anq06MFCf",
        "outputId": "bb873fd9-0d34-4331-fa33-570fa2662c59"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "10\n"
          ]
        }
      ],
      "source": [
        "## Method definition\n",
        "## Time complexity: O(n)\n",
        "## Space complexity: O(n) [n indicates the number of digits]\n",
        "def sum_of_digits(n):\n",
        "   ## base case condition\n",
        "    if n < 10:\n",
        "        return n\n",
        "    else:\n",
        "    ## recursive function call\n",
        "        return n % 10 + sum_of_digits(n // 10)\n",
        "\n",
        "\n",
        "## Driver code\n",
        "n = 1234\n",
        "result = sum_of_digits(n)\n",
        "print(result)"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "## Method definition\n",
        "## Time complexity: O(n)\n",
        "## Space complexity: O(n)\n",
        "\n",
        "def powerOf(a,n):\n",
        "  ## base case condition\n",
        "    if n==0:\n",
        "        return 1\n",
        "    else:\n",
        "    ## recursive function call\n",
        "        return a*powerOf(a,n-1)\n",
        "\n",
        "\n",
        "## Driver code\n",
        "a = 2\n",
        "n = 16\n",
        "result = powerOf(a, n)\n",
        "print(result)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "aDUCWXBrM-x3",
        "outputId": "2a121b0c-964d-41ec-d2cd-971c92ebcdd6"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "65536\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "## Method definition\n",
        "def powerFind(a, n):\n",
        "  ## base case condition\n",
        "  if n == 1:\n",
        "    return a\n",
        "\n",
        "  ## recursive function calls\n",
        "  else:\n",
        "    mid = n // 2\n",
        "    result = powerFind(a, mid)\n",
        "    finalResult = result * result\n",
        "\n",
        "    ## checking whether the value of n is even or odd\n",
        "    if n % 2 == 0:\n",
        "      return finalResult\n",
        "    else:\n",
        "      return a * finalResult\n",
        "\n",
        "## Driver code\n",
        "a = 2\n",
        "n = 19\n",
        "result = powerFind(a, n)\n",
        "print(result)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "_4BSHPzhTyex",
        "outputId": "145566a7-2d49-497c-9dac-04cc7b98f9a1"
      },
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "524288\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Task: https://leetcode.com/problems/powx-n/description/"
      ],
      "metadata": {
        "id": "8BwOF_YTZ0Ss"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "5//2"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lJiDyry6YZEx",
        "outputId": "9d44e338-f959-441e-8e8e-9503dbc08370"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "5/2"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "1DbJnAS2ajxb",
        "outputId": "079c9647-6c6c-489a-9f33-8803a7131033"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2.5"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "AuldAcE_alBt"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}