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

本文主要是介绍递归——简单粗暴的问题解决方式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

1 定义

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

2 例子

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

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

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

def binary_search_recursion(an, item, high, low):mid = int((low + high)/2)guess = an[mid]if guess == item:return mid + 1elif 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所取代了。

这篇关于递归——简单粗暴的问题解决方式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---