递归函数python经典例子
  递归函数是一种非常重要的编程技巧，它可以让我们在编写程序时更加高效和简洁。在Python中，递归函数的使用非常广泛，下面我们来看一些经典的例子。
 
  1. 阶乘函数
 
  阶乘函数是递归函数的经典例子之一。它的定义如下：
 
  ```
  def factorial(n):
      if n == 0:
          return 1
      else:
          return n * factorial(n-1)
  ```
 
  这个函数的作用是计算n的阶乘。当n等于0时，返回1；否则，返回n乘以n-1的阶乘。
 
  2. 斐波那契数列
 
  斐波那契数列也是递归函数的经典例子之一。它的定义如下：
 
  ```
  def fibonacci(n):
      if n == 0:
          return 0
      elif n == 1:
          return 1
      else:
          return fibonacci(n-1) + fibonacci(n-2)
  ```
 
  这个函数的作用是计算斐波那契数列的第n项。当n等于0时，返回0；当n等于1时，返回1；否则，返回斐波那契数列的第n-1项和第n-2项的和。
 
  3. 汉诺塔问题
 
  汉诺塔问题也是递归函数的经典例子之一。它的定义如下：
 
  ```
  def hanoi(n, A, B, C):
      if n == 1:
          print(A, "->", C)
      else:
          hanoi(n-1, A, C, B)
          print(A, "->", C)
          hanoi(n-1, B, A, C)
  ```
快速排序python实现
 
  这个函数的作用是解决汉诺塔问题。当n等于1时，直接将A柱子上的盘子移动到C柱子上；否则，先将A柱子上的n-1个盘子移动到B柱子上，然后将A柱子上的最后一个盘子移动到C柱子上，最后将B柱子上的n-1个盘子移动到C柱子上。
 
  4. 二分查
 
  二分查也是递归函数的经典例子之一。它的定义如下：
 
  ```
  def binary_search(arr, low, high, x):
      if high >= low:
          mid = (high + low) // 2
          if arr[mid] == x:
              return mid
          elif arr[mid] > x:
              return binary_search(arr, low, mid-1, x)
          else:
              return binary_search(arr, mid+1, high, x)
      else:
          return -1
  ```
 
  这个函数的作用是在有序数组arr中查元素x。如果到了，返回元素的下标；否则，返回-1。函数使用了递归的方式，每次将数组分成两半，然后在其中一半中查元素x。
 
  5. 快速排序
 
  快速排序也是递归函数的经典例子之一。它的定义如下：
 
  ```
  def quick_sort(arr):
      if len(arr) <= 1:
          return arr
      else:
          pivot = arr[0]
          left = [x for x in arr[1:] if x < pivot]
          right = [x for x in arr[1:] if x >= pivot]
          return quick_sort(left) + [pivot] + quick_sort(right)
  ```
 
  这个函数的作用是对数组arr进行快速排序。函数使用了递归的方式，每次选择一个基准元素，将数组分成两部分，然后对每一部分进行快速排序。
 
  6. 树的遍历
 
  树的遍历也是递归函数的经典例子之一。它的定义如下：
 
  ```
  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right
 
  def preorder_traversal(root):
      if root:
          print(root.val)
          preorder_traversal(root.left)
          preorder_traversal(root.right)
 
  def inorder_traversal(root):
      if root:
          inorder_traversal(root.left)
          print(root.val)
          inorder_traversal(root.right)
 
  def postorder_traversal(root):
      if root:
          postorder_traversal(root.left)
          postorder_traversal(root.right)
          print(root.val)
  ```
 
  这个函数的作用是对树进行前序遍历、中序遍历和后序遍历。函数使用了递归的方式，每次先遍历根节点，然后遍历左子树和右子树。
 
  7. 判断回文字符串
 
  判断回文字符串也是递归函数的经典例子之一。它的定义如下：
 
  ```
  def is_palindrome(s):
      if len(s) <= 1:

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。