How does these Pascal Triangle functions work?

Question

I'm reading Concepts, Techniques, and Models of Computer Programming, and there's a code at the beginning that I just cannot understand no matter how hard I try.

declare Pascal AddList ShiftLeft ShiftRight

fun {Pascal N}
   if N==1 then [1]
   else
      L in
      L = {Pascal N-1} % Recursion
      {AddList {ShiftLeft  L}
               {ShiftRight L}}
   end
end

fun {ShiftLeft L}
   case L of H|T then
      H|{ShiftLeft T}  % Recursion
   else [0]
   end
end

fun {ShiftRight L}
   0 | L
end

fun {AddList L1 L2}
   case L1 of H1|T1 then
      case L2 of H2|T2
      then
     H1+H2|{AddList T1 T2} % Recursion
      end
   else nil
   end
end

I kind of get the language constructs (this is the introduction to it), but the thing that really stands in my way is the recursion.

I'm trying to put a label on each recursion call that will abstractly say what goes in here, but I just can't figure it out.

What I ask for is a clear and easy explanations of how these functions work.

Answer 1

Start with N == 1: This is simple. The result is just [1].

Now check for N == 2:

First we calculate L = {Pascal N-1} = {Pascal 2-1} = {Pascal 1} = [1]
Now shifted to the left: [1 0]
Shifted to the right: [0 1]
AddList just adds elementwise. So the result for {Pascal 2} is [1 1].

Now for for N == 3:

{Pascal 2} = [1 1]
Shifted left:  [1 1 0]
Shifted right: [0 1 1]
Added:         [1 2 1]

Of course the program works the other way around: It starts with some larger N. But at the beginning of the Pascal function the program recurses repeatedly until the parameter N has become 1. Something like this:

{Pascal 3}
   {Pascal 2}
      {Pascal 1}
      [1]
   [1 1]
[1 2 1] 

Edit: There are actually to kinds of recursion in the program. The first one in Pascal starts with some integer N and recurses down to 1.

The other (in the helper methods) starts with a list consisting of a head and a tail and stops as soon as the list is empty, i.e. cannot be split anymore. (This is using so-called cons lists, an intrinsically recursive data type.)

Answer 2

wmeyer's explanation is very nice. I just want to add a possibly helpful 'visualization' -->

First of all, I'm using the original version of the book (PDF), I beleive, and the functions look like this -->

declare Pascal AddList ShiftLeft ShiftRight
fun {Pascal N}
   if N==1 then [1]
   else
      {AddList {ShiftLeft {Pascal N-1}} {ShiftRight {Pascal N-1}}}
   end
end

fun {ShiftLeft L}
   case L of H|T then
      H|{ShiftLeft T}
   else [0] end
end

fun {ShiftRight L} 0|L end

fun {AddList L1 L2}
   case L1 of H1|T1 then
      case L2 of H2|T2 then
         H1+H2|{AddList T1 T2}
      end
   else nil end
end

Imagine that you want to see row eight of Pascal's triangle. You are going to enter:

{Browse {Pascal 8}} 

i.e. you want to display the result of feeding 8 to the function Pascal as defined in the book/here.

First the function tests to see if the value it was just passed is 1 (which will not be true until the LAST iteration of the recursion (or the final recursive call(s)) at which time that [1] (from if N==1) will be returned as the output of THAT CALL OF Pascal and passed back up the 'chain' of executions (of Pascal) to the next most recent call first (where that result, [1], is added to the result of the matching ShiftLeft or ShiftRight, and then THAT result is sent back up the chain, and on and on, until it reaches the first one (Pascal 8). So the calls go 8 levels deep, then pass the answers back up those levels until you get the final answer... but I've jumped ahead.

Ok, since you fed an 8, the test N==1 fails, and therefore instead of being able to shift 'the lists' and add them together in the else clause right away, the function not being able to do that with undefined terms in the 'equations' says "I'll try N - 1! Maybe THAT will be the final answer!!" (for ShiftLeft AND ShiftRight - so this branching occurs each time the recursino happens)

So, the function waits for that answer from Pascal N-1 inside ShiftLeft and ShiftRight... waiting, waiting...

Well, {Pascal 7} won't be true for N==1 either, so the newer calls ("calls", 2nd AND 3rd calls, left and right!) of Pascal will BOTH also ask "What is Pascal N - 1" (7-1 this time) and they will both wait for the answer...

This goes on and on and on and on.... oh wait, until N==1!

Then [1], a list, is returned BACK UP THE CHAIN... so, each successive waiting function call, most recent first (keep in mind all these happen more and more on the way down to get here to the 'bottom' where N==1 as the splits increase (by calling ShiftLeft and ShiftRight at one time each call)) can finally make it's AddList calculation with the answers it has been waiting on from it's own personal, private calls to ShiftLeft and ShiftRight.

Everything goes all the way down to the bottom, splitting into more and more function calls, then we come back to the top and finally can get an answer returned. That final answer is the else clause of the first call to the Pascal function, {Pascal 8}, which now, inside, (since the 8th row of Pascal's triangle is [1 7 21 35 35 21 7 1]) will look like:

{AddList [1 7 21 35 35 21 7 0] [0 7 21 35 35 21 7 1]} <-- at least I think that's what the final lists to be added look like

Which once added is the one list returned as the final answer and displayed: [1 7 21 35 35 21 7 1]