**factorial**function can be defined in both

*recursive*and

*iterative*ways. Take a look at the following definitions borrowed from Wikipedia.

__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