Recursive definition:
Iterative definition:
For both the above definitions we have that:
The purpose here is not the mathematical stuff, but two provide the implementation of such definitions in Delphi (Object Pascal).
First, I bring you one recursive implementation of the factorial function. Notice how the function calls itself, which is what the recursion really is:
function Factorial(aNumber: Integer):
Integer
;
begin
if aNumber < 0 then
raise Exception.Create('
The factorial function is not
defined for negative integers.
');
Result:= 1;
if aNumber > 0 then
Result:= Factorial(aNumber-1) * aNumber;
end;
Second, I present you one iterative implementation of the factorial function. You can easily see the iteration performed in the “for” loop below:
function Factorial(aNumber:
Integer
):
Integer
;
var
i: Integer;
begin
if aNumber < 0 then
raise Exception.Create('
The factorial function is not
defined for negative integers.
');
Result:= 1;
for i:=1 to aNumber do
Result:= Result * i;
end;
Big-O considerations:
The recursive factorial function implemented before has a linear growth O(n), not O (n!). In addition, the iterative factorial function is also linear
O(n).
No comments:
Post a Comment