问题描述
我想知道分而治之的技术是否总是将问题分成相同类型的子问题?对于相同类型，我的意思是可以使用带有递归的函数来实现它.分治法总能用递归实现吗?
I wonder if the technique of divide and conquer always divide a problem into subproblems of same type? By same type, I mean one can implement it using a function with recursion. Can divide and conquer always be implemented by recursion?
谢谢！
推荐答案
总是"是一个可怕的词，但我想不出分而治之的情况，在这种情况下你不能使用递归.根据定义，分而治之会创建与初始问题形式相同的子问题 - 这些子问题不断分解，直到达到某个基本情况，并且划分的数量与输入的大小相关.递归是这类问题的自然选择.
"Always" is a scary word, but I can't think of a divide-and-conquer situation in which you couldn't use recursion. It is by definition that divide-and-conquer creates subproblems of the same form as the initial problem - these subproblems are continually broken down until some base case is reached, and the number of divisions correlates with the size of the input. Recursion is a natural choice for this kind of problem.
请参阅维基百科文章了解更多信息.
这篇关于分而治之和递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！