CODEWITHSUNDEEP
listerlang
SpecialSnowflake
SpecialSnowflake

Reputation: 995

Odd return when doing recursion on a list

Erlang noob here, I have a function which takes any number and breaks it down to separate digits in a list. Ex, 654 -> [6, 5, 4]

My code is as follows

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

digitize(0) ->
    [].

However the return is odd. FOr the input 654, the return will be: [[[[]|6]|5]|4]. What is wrong with my code?

Upvotes: 1

Views: 139

Answers (1)

mpm
mpm

Reputation: 3584

In short, you are returning too much lists :)

Sometimes when designing recursions, it is easier to thing about them from the end. This could make more sense, since it is the way the stack unwinds. So lets try to break down your example.

  • At the very end you digitize is called with 0. In that case it returns empty list [].
  • Then we jump level higher, where digitize was called with 6 (with sustituted[digitize(6 div 10)| (6 rem 10)];) when this empty list becomes head of list, (after substitution [ [] | 6];, which is returned to next level.
  • Than we unwind from call with 65 where again return value is created by [ [] | 6]; as head, and (65 rem 10) as tail. So again, we have list, which first element (head) is list, and second (tail) is one number (from rem)
  • And so on.

Hope you see the problem. Now lets try to find a solution, lets describe your algorithm. On each level of recursion you basically add (X rem 10), which is "smallest digit in X" to list of greater digits (recursion). Or to speak in programming terms, you append to list. The problem is that head-tailing is more like putting/poping from beginning, where Head is one element and Tail is a list. Fortunately there is lists:append/2 function, or even syntactic sugar that allows to add two list:

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

digitize(0) ->
    [].

And this works just fine.

Those are not really a problems, but we could improve on lack of tail recursion, and ++ operator which can be much less efficient than [H | T]. So we could invest little more effort in our function, and rewrite it like this:

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.

I would encourage you to investigate this code more, even if previous version is enough. Try to understand why this could be faster, why can we use head-tail, and why do we have to reverse list at the end. http://learnyousomeerlang.com/recursion is great start. Good luck!

Upvotes: 8

Related Questions