[erlang-questions] RV: Joe (final)

[Joe Armstrong]

There are two ways of thinking about recursion:

     1) Try to mentally execute the program
     2) Assume the program works, and look for a reduction step that
reduces the size
         of the argument and a base case

If you look at perms:

perms([]) -> [[]];
perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].


There is a base case   perms([])

the call to perms(L) involves a call to perms(L -- [H])

so there is a reduction step. If you call perms(L) it will call
perms(L--[H]) which is
a smaller argument than L. So for each call to perms the size of the
agument is reduced.
Eventually it will reach the base case [] and so it terminates.

Understanding recursion through method 1) (mental execution  of the program)
is terrible - your brain goes into a recursive loop. Often method 2) is
much easier.
Just check that the argument is reduced and that it will eventually reach
the base case
and that each reduction step is correct.

Cheers

/Joe

On Wed, Mar 6, 2013 at 12:30 AM, Ivan Carmenates García
<co7eb@REDACTED>wrote:

> ** **
>
> ** **
>
> *De:* Ivan Carmenates García [mailto:co7eb@REDACTED]
> *Enviado el:* martes, 05 de marzo de 2013 18:28
> *Para:* 'Danil Zagoskin'
> *Asunto:* RE: [erlang-questions] Joe (final)****
>
> ** **
>
> Hi, Danil, Joe, Richard,****
>
> ** **
>
> Well I think I finally did understand. The most tricky part was the
> swapping of the values.****
>
> ** **
>
> Here’s my understanding… ****
>
> ** **
>
> First I came up with an idea I tried this (it was before reading the
> Richard’s email lol)****
>
> ** **
>
> [[H,T] || H<-[1,2,3], T<-[1,2,3]] ****
>
> ** **
>
> and I could see that list of comprehension behave like nested for loops in
> imperative programming because it generate pair of numbers like this****
>
> ** **
>
> [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]****
>
> ** **
>
> So the most outer loop (the first generator) iterates only when the most
> inner loop (lasted generator) does the complete cycle. Now what list of
> comprehension does is that combines each item of the outer loop (first
> generator) with all the items of the second generator (inner loop) that’s
> why the head remains in many steps, like Joe says that I can stick for
> example the number 1 in each permutation of the rest of the list, and so on
> with the rest of the items in the list. ****
>
> ** **
>
> perms([]) -> [[]];****
>
> perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].****
>
> ** **
>
> Example:****
>
> ** **
>
> perms([1,2,3,4])->****
>
>             [ 1 | [ 2 | [ 3 | [ 4 | [[]] ] ] ] ] here the first recursive
> journey ends by returning an empty list within a list [[]]. So the value
> [[4]] is yielded ****
>
> Now the rolling back stands in the call to perms([3,4]) where the [[3,4]]
> list is emitted, [ H|T || H<-[3,4], T<-perms([4])  (this yield [[4]] ) ]
> (this yield [[3,4]])****
>
> So now the first generator has to advance to the second value in the list
> [3,4], because no more recursive call are made until now, and the second
> generator****
>
> only has one value (4) to yield, so the next value to yield for the first
> generator in the list [3,4] is 4, so H = 4, T = perms([3]) (which yield
> [[3]]) leading to the****
>
> list L’ = [[4, 3]] here is where the swap is made, that’s the part that I
> couldn’t understand before. So because there is no other value to retrieve
> in H from the****
>
> list [3,4] the evaluation of the comprehension list the and call to the
> function perms([3,4]) has ended yielding the list [[3,4], [4,3]] and
> rolling back to the call****
>
> of perms([2,3,4]) and so on…****
>
> ** **
>
>                 I’m alright? At least a fifty percent?****
>
> ** **
>
> ** **
>
> Danil’s last debug info really helped me to understand the last part.****
>
> ** **
>
> So Thanks all of you, for your help and time, uff it was really hard but
> finally I could archive knew knowledge that I hope will never forget.****
>
> … well that is if my understanding was at least fifty percent right! Lol.*
> ***
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20130306/45944f47/attachment.htm>