我将通过“归纳”设计一个Haskell数据结构来回答你的问题，这是递归的一种“对偶”。然后我会展示这种对偶性是如何带来好的结果的。

我们为简单树引入一个类型:

data Tree a = Branch (Tree a) (Tree a)
            | Leaf a
            deriving (Eq)

我们可以把这个定义理解为“一棵树是一个分支(包含两棵树)或一个叶子(包含一个数据值)”。叶结点是一种最小的情况。如果树不是叶子，那么它一定是包含两棵树的复合树。这些是唯一的例子。

让我们做一个树:

example :: Tree Int
example = Branch (Leaf 1) 
                 (Branch (Leaf 2) 
                         (Leaf 3))

现在，让我们假设我们想给树中的每个值加1。我们可以通过调用:

addOne :: Tree Int -> Tree Int
addOne (Branch a b) = Branch (addOne a) (addOne b)
addOne (Leaf a)     = Leaf (a + 1)

首先，请注意这实际上是一个递归定义。它将数据构造函数Branch和Leaf作为case(因为Leaf是最小值的，这是唯一可能的case)，我们可以确定函数将终止。

用迭代风格编写addOne需要什么?循环进入任意数量的分支会是什么样子?

此外，这种递归通常可以用“函子”来分解。我们可以通过定义将树变成函子:

instance Functor Tree where fmap f (Leaf a)     = Leaf (f a)
                            fmap f (Branch a b) = Branch (fmap f a) (fmap f b)

和定义:

addOne' = fmap (+1)

我们可以提出其他递归方案，例如代数数据类型的变形(或折叠)。使用变形法，我们可以这样写:

addOne'' = cata go where
           go (Leaf a) = Leaf (a + 1)
           go (Branch a b) = Branch a b

我认为在(非尾)递归中，每当函数被调用时，分配一个新的堆栈等都会受到性能影响(当然取决于语言)。

比较递归和迭代就像比较十字螺丝刀和一字螺丝刀。在大多数情况下，你可以拆卸任何一个平头的十字螺钉，但如果你使用专为该螺钉设计的螺丝刀，那就更容易了，对吧?

有些算法只是适合递归，因为它们的设计方式(斐波那契数列，遍历树状结构等)。递归使算法更简洁，更容易理解(因此可共享和可重用)。

此外，一些递归算法使用“惰性评估”，这使得它们比迭代算法更有效。这意味着它们只在需要的时候执行昂贵的计算，而不是每次循环运行时都执行。

这应该足够让你开始了。我也会给你找一些文章和例子。

链接1:Haskel vs PHP(递归vs迭代)

下面是一个程序员必须使用PHP处理大型数据集的示例。他展示了在Haskel中使用递归处理是多么容易，但由于PHP没有简单的方法来完成相同的方法，他被迫使用迭代来获得结果。

http://blog.webspecies.co.uk/2011-05-31/lazy-evaluation-with-php.html

链接2:掌握递归

递归的坏名声大多来自于命令式语言的高成本和低效率。本文的作者讨论了如何优化递归算法，使其更快、更有效。他还介绍了如何将传统循环转换为递归函数，以及使用尾部递归的好处。我认为他的结束语总结了我的一些要点:

递归编程为程序员提供了一种更好的组织方式 以一种既可维护又逻辑一致的方式编写代码。” https://developer.ibm.com/articles/l-recurs/

链接3:递归比循环快吗?(回答)

下面是一个与你的问题类似的stackoverflow问题的答案链接。作者指出，许多与递归或循环相关的基准测试都是特定于语言的。命令式语言通常使用循环更快，使用递归更慢，函数式语言反之亦然。我想从这个链接中得到的主要观点是，在语言不可知论/情境盲目的意义上回答这个问题是非常困难的。

递归比循环快吗?

递归的内存开销更大，因为每次递归调用通常都需要将一个内存地址推入堆栈，以便稍后程序可以返回到那个地址。

尽管如此，在许多情况下，递归比循环更自然、更可读——比如在处理树的时候。在这些情况下，我建议坚持使用递归。

你必须记住，使用太深的递归，你会遇到堆栈溢出，这取决于允许的堆栈大小。为了防止这种情况，请确保提供一些基本情况，以结束递归。

对于可以分解成多个更小的部分的问题，递归比迭代更好。

例如，要制作一个递归斐波那契算法，您将fib(n)分解为fib(n-1)和fib(n-2)，并计算这两部分。迭代只允许你一遍又一遍地重复一个函数。

然而，Fibonacci实际上是一个坏例子，我认为迭代实际上更有效。注意fib(n) = fib(n-1) + fib(n-2)和fib(n-1) = fib(n-2) + fib(n-3)。Fib (n-1)被计算了两次!

一个更好的例子是树的递归算法。分析父节点的问题可以分解为分析每个子节点的多个更小的问题。与斐波那契例子不同，较小的问题是相互独立的。

所以，对于那些可以分解成多个、更小、独立、相似问题的问题，递归比迭代更好。