递归 .ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPibD/eOqGzS9+1ljoUan3a",
      "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/github/zzqnot996/Data-structures-and-algorithms-python/blob/main/%E9%80%92%E5%BD%92%20.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 递归\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "n_H_UKRY44Sg"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### n的阶乘"
      ],
      "metadata": {
        "id": "mGhfVQpOG4jQ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 迭代版\n",
        "def FACTORIA(n):\n",
        "  result = 1\n",
        "  for i in range(1,n):\n",
        "    return i * result\n",
        "\n",
        "FACTORIAL(10)"
      ],
      "metadata": {
        "id": "l3_KUmHwD6yR",
        "outputId": "b5ea1fcb-803b-48cd-9f63-ff8aeed746a2",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3628800"
            ]
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "# 递归函数定义\n",
        "def FACTORIAL(N):\n",
        "\n",
        "  # 基础情况处理\n",
        "  if N == 0:\n",
        "    return 1\n",
        "  # 递归调用\n",
        "  temp = FACTORIAL(N-1)  # 每次让规模减小\n",
        "  # 递推到当前层\n",
        "  return temp*N\n",
        "\n",
        "\n",
        "FACTORIAL(10)"
      ],
      "metadata": {
        "id": "3fIfcx9P-Ylj",
        "outputId": "323f0f5a-54f5-4e50-e1d1-2fe2ea5355f8",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3628800"
            ]
          },
          "metadata": {},
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 斐波那契数列的第n项"
      ],
      "metadata": {
        "id": "3LYxsNN2593j"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 迭代版\n",
        "def FIBONACCI(n):\n",
        "  F_store = [0 for i in range(0,n)]\n",
        "  F_store[0] = 0\n",
        "  F_store[1] = 1\n",
        "  for i in range(2,n):\n",
        "    F_store[i] =  F_store[i-1] + F_store[i-2]\n",
        "  return F_store[n-1]\n",
        "FIBONACCI(4)"
      ],
      "metadata": {
        "id": "0g45JWXNEduV",
        "outputId": "648616e3-546a-4df7-c9b0-fff25bb22816",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {},
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# 递归版\n",
        "def FIBONACCI(n):\n",
        "  if n == 0:\n",
        "    return 0\n",
        "  elif n == 1:\n",
        "    return 1\n",
        "  else:\n",
        "    return FIBONACCI(n-1) + FIBONACCI(n-2)\n",
        "\n",
        "\n",
        "FIBONACCI(4)"
      ],
      "metadata": {
        "id": "Cgr5fssu6LeD",
        "outputId": "1e46f056-bc86-4419-8307-c94329c98790",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 归并排序\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "YTCkflMeGoEn"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# 迭代版\n",
        "\n"
      ],
      "metadata": {
        "id": "jShD2S04G9ar"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# 递归版\n",
        "# 将A[l...r-1]进行排序\n",
        "def Mergesort(A,l,r):\n",
        "\n",
        "  if  r-l <=1:\n",
        "    return\n",
        "  m = (l+r)//2\n",
        "  Mergesort (A,l,m)\n",
        "  Mergesort (A,m,r)\n",
        "  Merge(A,l,m,r)\n",
        "\n",
        "def Merge(A,l,m,r):\n",
        "\n",
        "\n",
        "\n",
        "sort_list = [8,1,7,4,5,2,3,6]"
      ],
      "metadata": {
        "id": "RtOAcUzaHCrD"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "id": "9Ah9kJWbciWq",
        "outputId": "a0972e3e-2f30-4d2d-dab8-70f027a03317"
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "'789456'"
            ],
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            }
          },
          "metadata": {},
          "execution_count": 14
        }
      ],
      "source": [
        "\n",
        "# 将整数转换成任意进制的字符串\n",
        "\n",
        "import math\n",
        "\n",
        "def recursion_num(num,base):\n",
        "\n",
        "  if num == 0:\n",
        "    return \"0\"\n",
        "\n",
        "  elif num  < 10:\n",
        "\n",
        "    return str(num)\n",
        "  else:\n",
        "    num_str = num % 10\n",
        "    return recursion_num(num//10,base) + str(num_str)\n",
        "\n",
        "\n",
        "\n",
        "recursion_num(789456,10)\n",
        "\n"
      ]
    }
  ]
}