在列表上进行递归时奇数返回

Question

Erlang noob在这里,我有一个函数,它接受任何数字并将其分解为单独的列表中的数字.Ex,654 - > [6,5,4]

我的代码如下

digitize(X) when X > 0 ->
    [digitize(X div 10)| (X rem 10)];

digitize(0) ->
    [].

然而,回报是奇怪的.对于输入654,返回将是:[[[[] | 6] | 5] | 4].我的代码出了什么问题？

Answer 1

总之,你回来的名单太多:)

有时在设计递归时,最终会更容易对它们进行处理.这可能更有意义,因为它是堆栈展开的方式.所以让我们试着打破你的榜样.

• 在最后你digitize被召唤0.在这种情况下,它返回空列表[].
• 然后我们跳得更高,当这个空列表成为列表的头部时,digitize调用with 6(带有取向[digitize(6 div 10)| (6 rem 10)];),(在替换之后[ [] | 6];,返回到下一级别).
• 比我们从呼叫中放松65,再次返回值由 [ [] | 6];头部和(65 rem 10)尾部创建.所以再次,我们有列表,第一个元素(头)是列表,第二个(尾)是一个数字(从rem)
• 等等.

希望你看到问题.现在让我们尝试找到一个解决方案,让我们描述你的算法.在每个递归级别,你基本上添加(X rem 10),这是"X中的最小数字"到更大的数字列表(递归).或者以编程术语发言,您可以附加到列表中.问题是头尾是更像是从头开始/弹出,其中Head是一个元素而Tail是一个列表.幸运的是有lists:append/2功能,甚至语法糖,允许添加两个列表:

digitize(X) when X > 0 ->
    digitize(X div 10) ++ [X rem 10];

digitize(0) ->
    [].

这很好用.

这些并不是真正的问题,但我们可以改进缺乏尾递归和++运算效率低得多的运算符[H | T].所以我们可以在我们的函数上投入更少的精力,并像这样重写它:

digitize(Int) ->
    lists:reverse(digitize(Int, _Acc = []).

digitize(Int, Acc) when X > 0 ->
    digitize(X div 10, [(X rem 10) | Acc]);
digitize(0, Acc) ->
    Acc.

我鼓励您更多地研究此代码,即使以前的版本已经足够了.试着理解为什么这会更快,为什么我们可以使用头尾,为什么我们必须在最后反转列表.http://learnyousomeerlang.com/recursion是一个很好的开始.祝好运!