Lecture 16: Recursive programming 

A much more interesting solution is if we define the function Factorial in terms of itself, just as we have learned in school,
n! = n*(n1)!
Let's do exactly that:
FUNCTION Factorial(n: integer): integer;
(* returns n! *)
begin
(* the value to be returned
is expressed in terms of itself: *)
Factorial := n*Factorial(n1);
end;
This function is already nearly correct. The only problem is that it will never stop calling itself. For instance, we can call it with Factorial(4), which will then try to calculate 4*Factorial(3) and hence call Factorial(3). Factorial(3) will try to calculate 3*Factorial(2), which will call Factorial(2), ... which will call Factorial(1) ... which will call Factorial(0) ... which will call Factorial(1) ... which will call Factorial(2) ... and this will never end. The program will never return anything and the computer will crash, probably generating a socalled "stack overflow" error. Clearly we have to build in a way to stop calling itself. Now remember that in the mathematical way of defining a function in terms of itself we also always had to build in a stop, for the Factorial function, this was 
1! = 1
Let's also built this into our function:
FUNCTION Factorial(n: integer): integer;
(* returns n! *)
begin
if n=1 then
Factorial := 1
else
Factorial := n*Factorial(n1);
end;
The idea we should learn from this is that we should give it a possibility
to come up with an answer and exit the recursive calculation. Just like
the way we had to give a loop the possibility to end we should also give
this possibilty to recursive functions. If not, the program will continue
forever (or crash).
We can implement this in a function, note the stopping condition:
FUNCTION Fibonacci(n: integer): integer;
begin
if (n=1) OR (n=2) then
Fibonacci := 1
else
Fibonacci := Fibonacci(n2)
+ Fibonacci(n1);
end;
Factorial(3) is called
a variable with name m is created
2*3 is assigned to it
Factorial(2) is called
a variable with name m is created
(different than m above!)
2*2 is assigned to it
Factorial(1) is called
a variable with name
m is created (different than the two above)
2*1 is assined to it
... we reach the stop
condition and Fortorial := 1;
The value of m is writen:
2
we exit Factorial(1)
The value of m is written: 4
we exit Factorial(2)
The value of m is written: 6
We exit Factorial(3)