[C++] Simple factorial algorithm

[ayu]

This is a "fun code" that we wrote during a not so fun lecture. It's not very long, most of the fun was done on paper.

Mathematical term is x!

Example: 3! = 3*2*1 = 6

Code: Select all

long long int Fakultet(int n)
{
       long long int sum = 1;

       for(; n>0; --n)
              sum*=n;

       return sum;
}

[leetnigga]

The English term is "Factorial". We use the same word as "Faculty" in Dutch too (faculteit)

Recursive version:

Code: Select all

long long int fact(int n)
{
  if (n == 0) return 1;
  return n * fact(n-1);
} 

Tail recursive version:

Code: Select all

long long int fact_i(int n, int product) {
  if(n == 1) return product;
  else return fact_i(n - 1, product*n);
}

long long int fact(int n) {
    if(n == 0) return 1;
    fact_i(n, 1);
}

[ayu]

heh yeah thanks for pointing that out leetnigga ^^

[Nerdz]

Nice to see people who knows about Tail recursivity. I don't see why would it be good to apply it here though

the problem with recursivity without being tail recursive is the stack overflow. Using the tail recursivity simply mean that when you found the answer, you jump directly back to the upper environement.

[Lundis]

I didn't know C++ supported tail-recursion!

I googled it and found this... thought it would be useful:
http://danzig.jct.ac.il/cpp/recursion.html

[leetnigga]

Nice to see people who knows about Tail recursivity. I don't see why would it be good to apply it here though

Because this is a classic example where the stack grows linearly. I forgot to give product the long long int type, by the way:

Code: Select all

long long int fact_i(int n, long long int product) {
  if(n == 1) return product;
  else return fact_i(n - 1, product*n);
}

long long int fact(int n) {
    if(n == 0) return 1;
    fact_i(n, 1);
} 

It's true that G++ is able to optimize this by itself.

the problem with recursivity without being tail recursive is the stack overflow. Using the tail recursivity simply mean that when you found the answer, you jump directly back to the upper environement.

Well, a regular recursive function winds the stack, executes the function, calls itself (which winds the stack, executes the function, calls itself, etc, etc) and unwinds (unwinds, unwinds, unwinds, etc, etc) when the answer is found. This will cause a stack overflow when the function calls itself too often.

A tail recursive function winds the stack once, executes the function, and when it needs to call itself (which is always the last operation in a tail-recursive function, because that's what makes a function tail-recursive) it simply jumps back to the start of the function (though after the winding of the stack). This way the overhead of pushing and popping stack frames all the time is removed.

[IceDane]

Nice to see people who knows about Tail recursivity. I don't see why would it be good to apply it here though

Because this is a classic example where the stack grows linearly. I forgot to give product the long long int type, by the way:

Code: Select all

long long int fact_i(int n, long long int product) {
  if(n == 1) return product;
  else return fact_i(n - 1, product*n);
}

long long int fact(int n) {
    if(n == 0) return 1;
    fact_i(n, 1);
} 

It's true that G++ is able to optimize this by itself.

the problem with recursivity without being tail recursive is the stack overflow. Using the tail recursivity simply mean that when you found the answer, you jump directly back to the upper environement.

Well, a regular recursive function winds the stack, executes the function, calls itself (which winds the stack, executes the function, calls itself, etc, etc) and unwinds (unwinds, unwinds, unwinds, etc, etc) when the answer is found. This will cause a stack overflow when the function calls itself too often.

A tail recursive function winds the stack once, executes the function, and when it needs to call itself (which is always the last operation in a tail-recursive function, because that's what makes a function tail-recursive) it simply jumps back to the start of the function (though after the winding of the stack). This way the overhead of pushing and popping stack frames all the time is removed.

Hmm, that is interesting. I didn't know that it g++ would optimize that out either. Any idea if other compilers do this automatically as well?

[l0ngb1t]

Recursive version:

Code: Select all

long long int fact(int n)
{
  if (n == 0) return 1;
  return n * fact(n-1);
} 

i think u r missing an else
hope that i'm right

Code: Select all

 if (n == 0) return 1; else 

without it, it will jump to the next next line of code even if n==0
am i right ????

[IceDane]

Recursive version:

Code: Select all

long long int fact(int n)
{
  if (n == 0) return 1;
  return n * fact(n-1);
} 

i think u r missing an else
hope that i'm right

Code: Select all

 if (n == 0) return 1; else 

without it, it will jump to the next next line of code even if n==0
am i right ????

Normally, yes. But "return 1;" terminates the function. So the else would be redundant in this case.

[l0ngb1t]

mmm yeah
apparently i missed the "return 1"

i should read carefully next time