递归——简单粗暴的问题解决方式

发布时间:2024年01月11日

相信很多人在刚接触算法时都在递归上栽过跟头(包括我),但是在掌握了这项技能后会有种豁然开朗的感觉!
我用我自己!
怎么会有这么优雅而又简单粗暴的解决问题的方法! \color{red}{怎么会有这么优雅而又简单粗暴的解决问题的方法!} 怎么会有这么优雅而又简单粗暴的解决问题的方法!

1 定义

没错,递归解决问题的思路就是“我用我自己”。
官方一点的解释是:递归(recursion)是一种在函数定义中使用函数自身的编程技术。在递归中,一个问题被分解为一个或多个更小的子问题,这些子问题与原始问题具有相同的结构。通过解决这些子问题,最终可以解决原始问题。

2 例子

沿用“二分查找”的例子,在原本的二分查找中,我们使用的是while循环的方法解决问题:

def binary_search_loop(an, item):
    low = 0
    high = len(an)-1

    while low <= high:
        mid = int((low + high)/2)
        guess = an[mid]
        if guess == item:
            return mid+1
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    pass

但是在一些编程语言中并没有类似于while的循环,这时递归便可派上用场:

def binary_search_recursion(an, item, high, low):
	mid = int((low + high)/2)
	guess = an[mid]

	if guess == item:
		return mid + 1
	elif guess > item:
		return binary_search_recursion(an, item, mid-1, low)
	else:
		return binary_search_recursion(an, item, high, mid+1)

在进行递归时,需要进行递归条件基线条件的判别。

2.1 基线条件

正如前文所述,递归是将一个问题被分解为一个或多个更小的子问题的过程,这是编程中极为重要的思想——分而治之(divide and conquer,D&C)。而基线条件对应的就是“最小的问题”,小到不可分。

...
if guess == item:
		return mid + 1
...

在代码中,当guess == item时,说明已经“猜”中了需要查找的元素,问题已经得到解决,而这个条件就是基线条件。

2.2 递归条件

...
	elif guess > item:
		return binary_search_recursion(an, item, mid-1, low)
	else:
		return binary_search_recursion(an, item, high, mid+1)
...

递归条件对应的是问题在没被解决时对应的条件,在例子中guess > item以及guess < item对应的都是问题还可拆分的情况,只不过后者被else所取代了。

文章来源:https://blog.csdn.net/SUN5_The_answer/article/details/135488775
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。