算法-递归和分治策略

本文最后更新于：2023年11月2日上午

递归

递归的概述

递归的定义

递归(Recursion)，又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。

Recursion从词源上分析只是"re- (again)" + "curs- (come, happen)" 也就是重复发生，再次重现的意思, 中文翻译 “递归”表达了两个意思：递＋归。

递归(Recursion)基本思想：把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数直接或间接调用它自身的情况。这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况。

应用场景：树、阶乘、Fibonacci数列、Hanoi塔问题

递归的性能问题：栈的分配和函数调用代价需要在具体工程实践中考虑。

递归的总体思想：

将求解的较大规模的问题分割成k个更小规模的子问题。

对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。

将求出的小规模的问题的解合并为一个更大规模的问题的解自底向上逐步求出原来问题的解。

分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，再各个击破，分而治之

直接或间接地调用自身的算法称为递归算法（直接递归间接递归）。用函数自身给出定义的函数称为递归函数。

边界条件与递归方程是递归函数的二个要素
递归函数只有具备这两个要素，才能在有限次计算后得出结果。

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。

分治与递归像一对挛生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。

递归、递推、迭代

递归形式的斐波那契数列：

//伪代码
int f[maxn] = 0;
f[0] = f[1] = 1;
int fib(int n){
	if(f[n]) return f[n];
	return f[n] = fib(n-1) + fib(n-2);
}

递推形式的斐波那契数列：

//伪代码
int f[maxn] = 0;
f[0] = f[1] = 1;
for(int i=2; i<=n; ++i){
	f[i] = f[i-1] + f[i-2]
}

递推Inductive ：一步步往后，从左往右。即有来无回。

递归Recursive：从最后面一步步往前嵌套，再从最前面一步步往后套。递归=递推+回归。即有来有回。

迭代Iteration：循环执行，每次把前面计算出的值套下一步。迭代是逐渐逼近，用新值覆盖旧值。

注意：递归次数太多可能会爆栈。

分治法的常用例子

二分查找

1. 概述

二分查找（Binary Search）算法，也叫折半查找算法

算法前件：待查找序列有序

基本思想：先将待查元素与中间元素比，若比中间元素大，则在序列的后一半继续查找；若比中间元素小，则在序列的前一半继续查找。

二分查找与顺序查找对比图：

2.复杂度分析

时间复杂度

我们假设数据大小是 n，每次查找后数据都会缩小为原来的一半，也就是会除以 2。最坏情况下，直到查找区间被缩小为空，才停止。

被查找区间的大小变化：n、n/2、n/4、n/8 ... n/2^k

假设总共查找了 k 次，则剩余 \(n/2^k\) 个元素。最坏的情况是查找到最后一个元素，则有等式：\(n/2^k = 1\)，即 \(2^k=n\)，得：\(k = log_2n\)

忽略常数，则二分查找的时间复杂度为O(log n)

空间复杂度

空间复杂度是很简单的，根据上面的流程可以得知，在整个二分搜索的过程中，只需要额外存储三个变量：最大值，最小值和中点，因此，空间复杂度是常量 O(1)

3. Python实现

# 二分查找的递归与分治策略实现（python）
def binary_search(arr, target, left, right):
    if left <= right:
        mid = left + (right - left) // 2  # 计算中间位置

        if arr[mid] == target:
            return mid  # 找到目标元素，返回索引
        elif arr[mid] < target:
            return binary_search(arr, target, mid + 1, right)  # 在右半部分递归查找
        else:
            return binary_search(arr, target, left, mid - 1)  # 在左半部分递归查找
    else:
        return -1  # 目标元素不在数组中，返回-1

# 输入数组
input_string = input("请输入一个升序数组（以逗号分隔）: ")
arr = list(map(int, input_string.split(',')))
print("已创建好一个升序数组：",arr)

# 输入要查找的数字
target = int(input("请输入要查找的数字: "))

result = binary_search(arr, target, 0, len(arr) - 1)

if result != -1:
    print(f"目标 {target} 在索引 {result}")
else:
    print(f"目标 {target} 不在数组中")

4. 应用场景及局限性

二分查找依赖顺序表结构，如数组；

那二分查找能否依赖其他数据结构呢？比如链表。答案是不可以的，主要原因是二分查找算法需要按照下标随机访问元素。数组按照下标随机访问数据的时间复杂度是 O(1)，而链表随机访问的时间复杂度是 O(n)。所以，如果数据使用链表存储，二分查找的时间复杂就会变得很高。
二分查找针对的是有序数据，如果无序，则要先排序；
数据量太小不适合二分查找；

如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。比如我们在一个大小为 10 的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多。

只有数据量比较大的时候，二分查找的优势才会比较明显。不过，这里有一个例外。如果数据之间的比较操作非常耗时，不管数据量大小，我都推荐使用二分查找。比如，数组中存储的都是长度超过 300 的字符串，如此长的两个字符串之间比对大小，就会非常耗时。我们需要尽可能地减少比较次数，而比较次数的减少会大大提高性能，这个时候二分查找就比顺序遍历更有优势。
数据量太大也不适合二分查找。

最后，数据量太大也不适合二分查找。

二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。比如，我们有 1GB 大小的数据，如果希望用数组来存储，那就需要 1GB 的连续内存空间。

注意这里的“连续”二字，也就是说，即便有 2GB 的内存空间剩余，但是如果这剩余的 2GB 内存空间都是零散的，没有连续的 1GB 大小的内存空间，那照样无法申请一个 1GB 大小的数组。而我们的二分查找是作用在数组这种数据结构之上的，所以太大的数据用数组存储就比较吃力了，也就不能用二分查找了。