循环和递归之间有什么实际区别

Question

我目前正在使用PHP,因此这个示例将使用PHP,但问题适用于多种语言.

我和我的一个恶魔一起在这个项目上工作,而且一如既往我们被一个大问题所困扰.现在我们都回家了,无法解决问题.那天晚上我们都找到了解决方案,只是我使用了一个循环来解决问题,他使用了递归.

现在我想告诉他循环和递归之间的区别,但我无法想出一个解决方案,你需要通过正常循环递归.

我将制作两者的简化版本,我希望有人可以解释一个人与另一个人的不同之处.

如果有任何编码错误,请原谅我

循环:

printnumbers(1,10);

public function printnumbers($start,$stop)
{
    for($i=$start;$i<=$stop;$i++)
    {
        echo $i;
    }
}

现在上面的代码只是打印出数字.

现在让我们通过递归来做到这一点:

printnumbers(1,10);

public function printnumbers($start,$stop)
{
    $i = $start;
    if($i <= $stop)
    {
        echo $i;
        printnumbers($start+1,$stop);
    }
}

上面的这个方法与循环完全相同,但只有递归.

任何人都可以向我解释使用这些方法之一有什么不同.

Answer 1

循环和递归在很多方面都是等价的.没有程序需要一个或另一个,原则上你总是可以从循环转换为递归,反之亦然.

递归更强大,因为将递归转换为循环可能需要一个必须自己操作的堆栈.(尝试使用循环遍历二叉树,您会感到痛苦.)

另一方面,许多语言(和实现)(例如Java)不能正确地实现尾递归.尾递归是指你在函数中做的最后一件事就是自己调用(就像在你的例子中一样).这种递归不必消耗任何堆栈,但在许多语言中它们都会消耗,这意味着您不能总是使用递归.

Answer 2

通常,使用递归更容易表达问题.当你谈论树状数据结构(例如目录,决策树......)时尤其如此.

这些数据结构本质上是有限的,因此处理它们的大部分时间在递归时更加清晰.

当堆栈深度经常受到限制,并且每个函数调用都需要一个堆栈时,并且在谈论可能无限的数据结构时,您将不得不放弃递归并将其转换为迭代.

特别是函数式语言擅长处理"无限"递归.命令式语言专注于类似迭代的循环.