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;
}
Code: Select all
long long int Fakultet(int n)
{
long long int sum = 1;
for(; n>0; --n)
sum*=n;
return sum;
}
Code: Select all
long long int fact(int n)
{
if (n == 0) return 1;
return n * fact(n-1);
}
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);
}
Because this is a classic example where the stack grows linearly. I forgot to give product the long long int type, by the way:Nerdz wrote:Nice to see people who knows about Tail recursivity. I don't see why would it be good to apply it here though
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);
}
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.Nerdz wrote: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.
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?leetnigga wrote:Because this is a classic example where the stack grows linearly. I forgot to give product the long long int type, by the way:Nerdz wrote:Nice to see people who knows about Tail recursivity. I don't see why would it be good to apply it here though
It's true that G++ is able to optimize this by itself.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); }
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.Nerdz wrote: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.
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.
i think u r missing an elseleetnigga wrote: Recursive version:Code: Select all
long long int fact(int n) { if (n == 0) return 1; return n * fact(n-1); }
Code: Select all
if (n == 0) return 1; else
Normally, yes. But "return 1;" terminates the function. So the else would be redundant in this case.l0ngb1t wrote:i think u r missing an elseleetnigga wrote: Recursive version:Code: Select all
long long int fact(int n) { if (n == 0) return 1; return n * fact(n-1); }
hope that i'm rightCode: 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 ????