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.
Start with N == 1: This is simple. The result is just
[1]
.Now check for N == 2:
Now for for N == 3:
Of course the program works the other way around: It starts with some larger
N
. But at the beginning of thePascal
function the program recurses repeatedly until the parameterN
has become1
. Something like this:Edit: There are actually to kinds of recursion in the program. The first one in
Pascal
starts with some integerN
and recurses down to1
.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.)