Python递归函数-常见算法应用

Python中的递归函数是一种特殊的函数，它可以调用自身执行某个任务。递归函数既可以简化代码，又可以实现某些算法，例如：斐波那契数列、递归排序、二叉树遍历等。

一、斐波那契数列

斐波那契数列是指：0、1、1、2、3、5、8、13、21、34、……，在数学上，斐波那契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F（n-1）+F（n-2）（n>=2， n∈N * ）。

Python递归程序实现斐波那契数列：

def fib(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

n = int(input("请输入斐波那契第n项："))
print("斐波那契第%d项为：" % n, fib(n))

二、递归排序

递归排序是一种基于分治的算法，在Python中可使用递归函数实现。递归排序的基本思想：将原问题分成若干子问题，分别求解各子问题，最终合并各子问题的解得到原问题的解。

Python递归程序实现递归排序：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

arr = [5, 3, 1, 6, 8, 4, 9, 2, 7]
print("排序前：", arr)
print("排序后：", quick_sort(arr))

三、二叉树遍历

二叉树是指每个节点最多有两个子节点的树结构，二叉树的遍历包括前序遍历、中序遍历和后序遍历三种方式。在Python中可以使用递归函数实现二叉树的遍历算法。

Python递归程序实现二叉树的前序遍历：

class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root):
        if not root:
            return []
        return [root.val] + preorderTraversal(root.left) + preorderTraversal(root.right)

root = Node(1, Node(2), Node(3, Node(4), Node(5)))
print("二叉树的前序遍历结果为：", preorderTraversal(root))

以上是三种常见算法的Python递归函数实现方法，递归函数的精髓在于它能通过自己的调用来解决问题，每次递归向下，问题规模逐渐变小，最终达到终止条件并返回结果。在编写递归程序时需要避免出现死递归的情况，也要注意递归函数可能引起的栈溢出问题。