递归算法

思考

一个正整数的阶乘（n!=1×2×3×...×(n-1)×n）是所有小于及等于该数的正整数的积，并且0的阶乘为1。如果要用循环实现一个阶乘，应该如何实现？

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

但使用循环实现的问题在于，代码和数学公式并没有一个清晰的对应关系。那是否有看起来过程更清晰的表达方式？

def factorial_recursive(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial_recursive(n - 1)

什么情况可以使用递归？

有非常多的算法和数据结构可以用到递归算法：

数学公式：求阶乘、斐波那契数列。
二分查找。
快速排序。
二叉树的遍历。

什么是递归算法

递归算法是一种在问题求解过程中调用自身的算法。（自己调用自己）
递归算法使用条件： 1. 一个问题可以拆分成子问题。 1. 这些问题求解思路相同，数据规模不同。 1. 拥有明确的终止条件。
递归算法通常包含两个主要组成部分： - 基线条件。 - 递归条件。

递归算法的实现

在实现递归算法的过程中，需要先明确需求对应的基线条件和递归条件是什么。

递归条件是指算法在处理问题时，通过调用自身来解决规模较小的子问题。递归情况下，问题的规模逐渐减小，直到达到基本情况。
基线条件是指能够直接解决的最小子问题。当算法达到基本情况时，不再进行递归调用，而是返回结果或执行其他操作。

实现一个倒计时的函数

倒计时函数的业务逻辑非常简单，传入一个参数，并且打印每个倒数的数字，直到0为止。如果用递归的思路实现：

确定递归条件：比如倒计时如果分解问题，代表每次调用方法的时候，参数都要-1。即可实现数字递减的过程。

# 死循环的递归
def countdown(i):
    print(i)
    # 递归条件
    countdown(i-1)

注意：以上的代码是不正确的，因为会无限死循环，所以需要制定一个中止条件，也就是基线条件。

确定基线条件：倒计时函数结束条件为，当倒数的数字为0，或小于0的时候自然就结束了。

def countdown(i)
    print(i)
    if i<= 0:
        # 基线条件
        return
    else:
        # 递归条件
        countdown(i-1)

所有的递归算法在编写的时候，都可以按照这个思路进行实现。

分而治之（D&C）

在了解到递归的基本思路之后，就可以探索一种著名的递归式问题解决方案——分而治之。

什么是分而治之（D&C）

简单来说，分而治之解决问题的过程包括两个步骤：

找出基线条件。
不断将问题分解，直到符合基线条件。

案例

需求说明：

编写一个递归函数来计算列表包含的元素数。
通过递归找到列表中最大的数字。
通过递归的方式实现二分查找算法。

如果用递归实现，思路是什么呢？

找出基线条件：数组为一个空数组，或只有一个元素。
不断将问题分解，直到符合基线条件：将数组不停地减小，直到符合基线条件为止。

源码实现（Python）

# 1. 编写一个递归函数来计算列表包含的元素数。
def count_item(data_list, count):
    if data_list == []:
        return count
    data_list.pop(0)
    count += 1
    # 递归条件
    return count_item(data_list, count)



def test_count_item():
    assert count_item([1,2,3,4,5], 0) == 5

# 1. 通过递归找到列表中最大的数字。
def find_max_number(data_list, max_data):
    # 基线条件
    if data_list == []:
        return max_data
    delete_item = data_list.pop(0)
    if max_data < delete_item:
        max_data = delete_item
    # 递归条件
    return find_max_number(data_list, max_data)

def test_find_max_number():
    data_list = [1,2,3,4,5]
    assert find_max_number(data_list, data_list[0]) == 5

# 1. 通过递归的方式实现二分查找算法。
def binary_search(data_list, low, high, target):
    # 基线条件：函数不再调用自己。
    if low>high:
        return -1
    # 基线条件：获取到中间元素，停止递归，返回中间值索引
    mid = (low+high)//2
    if data_list[mid] == target:
        return mid
    # 递归条件：目标值> 中间值
    if target> data_list[mid]:
        low = mid +1
    # 递归条件：目标值< 中间值
    else:
        high= mid -1
    return binary_search(data_list, low, high, target)

def test_binary_search():
    assert binary_search([1,2,3,4,5,6,7,8], 5) == 4
    assert binary_search([1,2,3,4,5], 1) == 0
    assert binary_search([1,2,3,4,5], 9) == -1

源码实现（Java）

public class Recursion {
//    通过递归找到列表中最大的数字。
    public int getSum(int [] nums, int sum, int currentIndex){
        if (currentIndex==nums.length){
            return sum;
        }
        sum += nums[currentIndex];
        currentIndex += 1;
        return getSum(nums, sum, currentIndex);
    }
//    通过递归找到列表中最大的数字。
    public int getMax(int [] nums, int maxData, int currentIndex){
        if (currentIndex==nums.length){
            return maxData;
        }
        if (nums[currentIndex] > maxData){
            maxData = nums[currentIndex];
        }
        currentIndex += 1;
        return getMax(nums, maxData, currentIndex);
    }
    // 递归版本的二分查找
    public int recurisonBinarySearch(int [] nums, int target ,int minIndex , int maxIndex, int mid){
        mid = (minIndex+maxIndex)/2;
        if (nums[mid] == target){
            return mid;
        }
        if (minIndex>maxIndex){
            return -1;
        }
        if (nums[mid]>target) {
            maxIndex = mid - 1;
        }else {
            minIndex = mid + 1;
        }
        return recurisonBinarySearch(nums, target, minIndex, maxIndex, mid);
    }
}

// 测试用例
class RecursionTest {
    static Recursion recursion;
    @BeforeAll
    static void setupClass(){
        recursion = new Recursion();
    }

    @Test
    void getSum() {
        int [] xx = {1,2,3,4,5};
        int [] xx2 = {1,2,3,4,5,6,7};
        assertEquals(recursion.getSum(xx, 0, 0) , 15);
        assertEquals(recursion.getSum(xx2, 0, 0) , 28);
    }

    @Test
    void getMax() {
        int [] xx = {1,2,3,4,5};
        int [] xx2 = {1,2,3,4,5,6,7};
        assertEquals(recursion.getMax(xx, xx[0], 0) , 5);
        assertEquals(recursion.getMax(xx2, xx2[0], 0) , 7);
    }

    @Test
    void recurisonBinarySearch() {

        int[] arr = {11, 22, 33, 44, 55, 66, 77};
        int[] arr2 = {11, 22, 33, 44, 55, 66, 77, 88};
        assert recursion.recurisonBinarySearch(arr, 33, 0, arr.length - 1, 0) == 2;
        // 不存在的场景
        assert recursion.recurisonBinarySearch(arr, 99, 0, arr.length- 1, 0) == -1;
        // 边界值
        assert recursion.recurisonBinarySearch(arr, 11, 0, arr.length- 1, 0) == 0;
        assert recursion.recurisonBinarySearch(arr, 77, 0, arr.length- 1, 0) == 6;
        assert recursion.recurisonBinarySearch(arr2, 88, 0, arr2.length- 1, 0) == 7;
    }
}

递归算法

递归算法

思考

什么情况可以使用递归 ？

什么是递归算法

递归算法的实现

实现一个倒计时的函数

分而治之（D&C）

什么是分而治之（D&C）

案例

源码实现（Python）

源码实现（Java）

什么情况可以使用递归？