Logo

Programming-Idioms

History of Idiom 31 > diff from v18 to v19

Edit summary for version 19 by :
↷

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