Programming-Idioms

History of Idiom 31 > diff from v18 to v19

Edit summary for version 19 :

Version 18

2015-09-09, 09:02:00

Version 19

2015-10-29, 14:05:13

Idiom #31 Recursive factorial (simple)

Create recursive function f which returns the factorial of non-negative integer i, calculated from f(i-1)

Idiom #31 Recursive factorial (simple)

Create recursive function f which returns the factorial of non-negative integer i, calculated from f(i-1)

Code
f i = if i > 1 then f (i-1) * i else 1
Code
f i = if i > 1 then f (i-1) * i else 1
Code
f = Hash.new { |hash, i| hash[i] = i * hash[i -1] }
f[0] = 1
f[23] # => 25852016738884976640000
Code
f = Hash.new { |hash, i| hash[i] = i * hash[i -1] }
f[0] = 1
f[23] # => 25852016738884976640000
Comments bubble
Note that f is not a function but plain old Hash used as a cache for performance.
Comments bubble
Note that f is not a function but plain old Hash used as a cache for performance.
Code
type
  TPositiveInt = 0..MaxInt;

function _f(_i: TPositiveInt): Integer;
begin
  if (_i < 2) then
    Result := 1
  else
    Result := _f(_i - 1);
end; 
Code
type
  TPositiveInt = 0..MaxInt;

function _f(_i: TPositiveInt): Integer;
begin
  if (_i < 2) then
    Result := 1
  else
    Result := _f(_i - 1);
end; 
Comments bubble
The definition of type TPositiveInt allows for rangechecking on the input.
MaxInt is already defined in the language.
Comments bubble
The definition of type TPositiveInt allows for rangechecking on the input.
MaxInt is already defined in the language.
Code
unsigned int f(unsigned int i)
{
	return i?i*f(i-1):1;
}
Code
unsigned int f(unsigned int i)
{
	return i?i*f(i-1):1;
}
Comments bubble
Overflows for i>20 in 64bits and for i>12 in 32bits
Comments bubble
Overflows for i>20 in 64bits and for i>12 in 32bits
Code
function f(n) {
   return n<2 ? 1 : n * f(n-1);
}
Code
function f(n) {
   return n<2 ? 1 : n * f(n-1);
}
Code
sub f {
   my $n = shift;
   return $n<2 ? 1 : $n * f($n-1);
}
Code
sub f {
   my $n = shift;
   return $n<2 ? 1 : $n * f($n-1);
}
Code
int f(int i){
	if(i==0)
		return 1;
	else
		return i * f(i-1);
} 
Code
int f(int i){
	if(i==0)
		return 1;
	else
		return i * f(i-1);
} 
Comments bubble
Warnings :
- type int quickly overflows
- high number of recursive calls may cause a stack overflow
- also, f is not tail-recursive
Comments bubble
Warnings :
- type int quickly overflows
- high number of recursive calls may cause a stack overflow
- also, f is not tail-recursive
Demo URL
http://ideone.com/G8eCnz
Demo URL
http://ideone.com/G8eCnz