There are two ways of thinking about recursion:<br><br>     1) Try to mentally execute the program<br>     2) Assume the program works, and look for a reduction step that reduces the size<br>         of the argument and a base case<br>

<br>If you look at perms:<br><br><p class="MsoNormal" style="text-autospace:none"><span style="font-size:10.0pt;font-family:"Courier New"">perms([]) -> [[]];</span></p><span style="font-size:10.0pt;font-family:"Courier New"" lang="EN-US">perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].</span><br>
 <br><br>There is a base case   perms([])<br><br>the call to perms(L) involves a call to perms(L -- [H])<br><br>so there is a reduction step. If you call perms(L) it will call perms(L--[H]) which is<br>a smaller argument than L. So for each call to perms the size of the agument is reduced.<br>
Eventually it will reach the base case [] and so it terminates.<br><br>Understanding recursion through method 1) (mental execution  of the program)<br>is terrible - your brain goes into a recursive loop. Often method 2) is much easier.<br>
Just check that the argument is reduced and that it will eventually reach the base case<br>and that each reduction step is correct.<br><br>Cheers<br><br>/Joe<br><br><div class="gmail_quote">On Wed, Mar 6, 2013 at 12:30 AM, Ivan Carmenates García <span dir="ltr"><<a href="mailto:co7eb@frcuba.co.cu" target="_blank">co7eb@frcuba.co.cu</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div link="blue" vlink="purple" lang="ES"><div><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><u></u> <u></u></span></p><div><div style="border:none;border-top:solid #b5c4df 1.0pt;padding:3.0pt 0cm 0cm 0cm">

<p class="MsoNormal"><b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">De:</span></b><span style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Ivan Carmenates García [mailto:<a href="mailto:co7eb@frcuba.co.cu" target="_blank">co7eb@frcuba.co.cu</a>] <br>

<b>Enviado el:</b> martes, 05 de marzo de 2013 18:28<br><b>Para:</b> 'Danil Zagoskin'<br><b>Asunto:</b> RE: [erlang-questions] Joe (final)<u></u><u></u></span></p></div></div><p class="MsoNormal"><u></u> <u></u></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">Hi, Danil, Joe, Richard,<u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"><u></u> <u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">Well I think I finally did understand. The most tricky part was the swapping of the values.<u></u><u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">Here’s my understanding… <u></u><u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">First I came up with an idea I tried this (it was before reading the Richard’s email lol)<u></u><u></u></span></p>

<p class="MsoNormal"><span lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-family:"Courier New"" lang="EN-US">[[H,T] || H<-[1,2,3], T<-[1,2,3]] <u></u><u></u></span></p><p class="MsoNormal">

<span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">and I could see that list of comprehension behave like nested for loops in imperative programming because it generate pair of numbers like this<u></u><u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US">[[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]<u></u><u></u></span></p>

<p class="MsoNormal"><span lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">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. <u></u><u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span lang="EN-US">perms([]) -> [[]];<u></u><u></u></span></p>

<p class="MsoNormal"><span lang="EN-US">perms(L) -> [[H|T] || H <- L, T <- perms(L--[H])].<u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"><u></u> <u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">Example:<u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"><u></u> <u></u></span></p>

<p class="MsoNormal"><span lang="EN-US">perms([1,2,3,4])-><u></u><u></u></span></p><p class="MsoNormal"><span lang="EN-US">            [ 1 | [ 2 | [ 3 | [ 4 | [[]] ] ] ] ]</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"> here the first recursive journey ends by returning an empty list within a list [[]]. So the value [[4]] is yielded <u></u><u></u></span></p>

<p class="MsoNormal" style="text-indent:35.4pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">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]])<u></u><u></u></span></p>

<p class="MsoNormal" style="text-indent:35.4pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">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<u></u><u></u></span></p>

<p class="MsoNormal" style="text-indent:35.4pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">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<u></u><u></u></span></p>

<p class="MsoNormal" style="text-indent:35.4pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">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<u></u><u></u></span></p>

<p class="MsoNormal" style="text-indent:35.4pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">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<u></u><u></u></span></p>

<p class="MsoNormal" style="text-indent:35.4pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">of perms([2,3,4]) and so on…<u></u><u></u></span></p><p class="MsoNormal">

<span lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal" style="text-indent:35.4pt"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">                I’m alright? At least a fifty percent?<u></u><u></u></span></p>

<div><div><p class="MsoNormal"><span lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"><u></u> <u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">Danil’s last debug info really helped me to understand the last part.<u></u><u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">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.<u></u><u></u></span></p>

<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d" lang="EN-US">… well that is if my understanding was at least fifty percent right! Lol.</span><span lang="EN-US"><u></u><u></u></span></p>

</div></div></div></div><br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br>