递归算法，读这篇文章或许更有启发

递归是一种算法技巧，它允许在函数内部调用自己。递归算法通常用于解决分治问题，即将大问题分解为若干个小问题，然后递归地解决这些小问题。最后将所有小问题的答案合并得到大问题的答案。递归算法需要确定一个终止条件，以防止函数无限递归。

递归算法几个例子：

1. 斐波那契数列：递归算法可以用来求斐波那契数列的第n项。这个算法的终止条件是n=1或n=2，其余情况则递归求解。
2. 求阶乘：递归算法可以用来求n的阶乘。这个算法的终止条件是n=1，其余情况则递归求解。
3. 求解汉诺塔问题：递归算法可以用来解决汉诺塔问题。这个算法的终止条件是只剩一个盘子，其余情况则递归求解。
4. 二分查找：递归算法可以用来实现二分查找算法。这个算法的终止条件是找到目标元素或查找区间为空，其余情况则递归求解。
5. 遍历二叉树: 递归算法可以用来遍历二叉树。终止条件是遍历到叶子节点。

　　1、斐波那契数列：

　　def fibonacci(n):

  　　  if n == 1 or n == 2:

     　　   return 1

  　　  else:

     　　   return fibonacci(n-1) + fibonacci(n-2)

　　2、求阶乘：

　　def factorial(n):

 　　   if n == 1:

      　　  return 1

  　　  else:

      　　  return n * factorial(n-1)

　　3、求解汉诺塔问题：

　　def hanoi(n, src, dst, tmp):

 　　   if n == 1:

       　　 print(f”move disk {n} from {src} to {dst}”)

 　　   else:

      　　  hanoi(n-1, src, tmp, dst)

    　　    print(f”move disk {n} from {src} to {dst}”)

    　　    hanoi(n-1, tmp, dst, src)

　　4、二分查找：

　　def binary_search(arr, target, low, high):

  　　  if low > high:

      　　  return -1

 　　   else:

     　　   mid = (low + high) // 2

      　　  if arr[mid] == target:

          　　  return mid

       　　 elif arr[mid] < target:

          　　  return binary_search(arr, target, mid+1, high)

     　　   else:

         　　   return binary_search(arr, target, low, mid-1)

　　5、遍历二叉树：

　　class Node:

   　　 def __init__(self, val):

       　　 self.val = val

      　　  self.left = None

       　　 self.right = None

　　def preorder_traversal(root):

  　　  if root is None:

      　　  return

  　　  print(root.val)

   　　 preorder_traversal(root.left)

  　　  preorder_traversal(root.right)