Calculating the factorial of a number in Delphi: Recursive and iterative methods

The factorial function can be defined in both recursive and iterative ways. Take a look at the following definitions borrowed from Wikipedia.

Recursive definition:

Factorial Recursive definition







Iterative definition:

Factorial Iterative Definition





For both the above definitions we have that:

Zero Factorial



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

Post a Comment