Function return

[Esso]

This func. calculates factorials
what I don't understand is how it keeps the values 5*4*3*2*1, while else says return 1, who it doesn't store 1 that coming from else and it keeps the former values?

factor2.cpp //calculates factorials using recursion #include <iostream> using namespace std; unsigned long factfunc(unsigned long);  //declaration int main() { int n;                //number entered by user unsigned long fact;   //factorial cout << “Enter an integer: “; cin >> n; fact = factfunc(n); cout << “Factorial of “ << n << “ is “ << fact << endl;    return 0; }   

unsigned long factfunc(unsigned long n) 
{ if(n > 1) return n * factfunc(n-1);  / else return 1; }

  

[Ganado]

What on earth is that comment and indentation?

To actually answer your question (I think), the memory is due to a new stack frame each time the function is called recursively.

e.g. n = 3

factfunc(3)
{
    (3 > 1)
        return 3 * factfunc(2)
        {
            (2 > 1)
                return 2 * factfunc(1)
                {
                    (else)
                        return 1;
                }
        }
}

Each time you recurse, you add a new stack frame, and this keeps the state of the outer call. So once you reach the "return 1;", you'll stop recursing and you'll eventually get 3 * 2 * 1.

In general, if you nest the recursion too deep, you can get a "stack overflow" because you pushed too many levels to the stack.

[TheToaster]

There shouldn't be a / before the else.

[Esso]

I'm sorry for copy past!
This is it:

int main ()
{
unsigned long factfunc (unsigned long);
unsigned long fact;
int n;
cout<<"Enter an integer";
cin>>n;
fact = factfunc(n);
cout<<"Factorial of "<<n<<" is "<<fact;
return 0;
}
unsigned long factfunc (unsigned long n)
{
if (n>1)
return n * factfunc (n-1);
else
return 1;
}

So Ganado, do you mean it's as if
While (n>1)
return n * factfunc (n-1); ??

[jonnin]

recursion uses the program call stack as if it were a stack data structure.

you call fact(5).
it stops to call fact(4), but like all function calls, the state of the current function is pushed onto the stack and preserved. fact(4) calls 3, 2, 1 and hits the condition where it just returns 1 because of the line 14 condition. 1 returns to where it was, back in fact(2) which multiplies the result (1) and the current value (2) and returns that (2). that returns to where it was in fact(3) and multiplies to get 6, and so on.

you can probably find an animated how it works online with a little searching.

[Ganado]

Esso, not exactly. Using a loop would be iteration as opposed to recursion.
jonnin's description of the state getting pushed onto the stack is more accurate.

[Esso]

Thanks a lot all of you, guys!
But, where should I search exactly for such
purpose, Jonnin?

[highwayman]

Maybe this? https://www.youtube.com/watch?v=ygK0YON10sQ

[Esso]

highwayman ... thanks a lot man!
Thanks a thousand to all of you good people!

[Esso]

Guys ... I was trying to figure it out
how does this statement (else return 1;)
doesn't make the condition passes through it and give the whole function the value (1) at the end of time, so...
When I replaced 1 with 2 (else return 2;), it gave me 240 (assuming n = 5 ), and the most thing that surprised me that when I replced the 1 with n (else return n;), the output was just correct as if I didn't replaced the 1 by n!!

You probably now think I'm an idiot and I won't blame you ... I'm still rookie and I'm 0 at math!

[Enoizat]

I'm still rookie and I'm 0 at math!

This is the beginners’ forum and everybody is assumed to be a rookie. I’m 0 at math too, but very little math is involved here: it’s just a multiplication.

What cannot be accepted is not spending any time to properly indent one’s code. No C++ guru writes badly indented code, and beginners shouldn’t too.

To understand recursive functions, the trick is always the same: observe them while they are working, don’t try to guess everything inside your mind only.

Try to read the output of this version of your code:

#include <iostream>


unsigned long factfunc (unsigned long);


int main ()
{
    std::cout << "Please enter an integer: ";
    int n;
    std::cin >> n;
    unsigned long fact = factfunc( n );
    std::cout << "\n\nmain() --> Factorial of " << n << " is " << fact << '\n';
    return 0;
}


unsigned long factfunc (unsigned long n)
{
    std::cout << "factfunc() --> n: " << n;
    if (n > 1) {
        std::cout << "\tcalling: " << n << " * factfunc( " << n - 1 << " )\n";
        return n * factfunc( n - 1 );
    } else {
        std::cout << "\treturning 1\n";
        return 1;
    }
}

Output:

Please enter an integer: 15
factfunc() --> n: 15    calling: 15 * factfunc( 14 )
factfunc() --> n: 14    calling: 14 * factfunc( 13 )
factfunc() --> n: 13    calling: 13 * factfunc( 12 )
factfunc() --> n: 12    calling: 12 * factfunc( 11 )
factfunc() --> n: 11    calling: 11 * factfunc( 10 )
factfunc() --> n: 10    calling: 10 * factfunc( 9 )
factfunc() --> n: 9     calling: 9 * factfunc( 8 )
factfunc() --> n: 8     calling: 8 * factfunc( 7 )
factfunc() --> n: 7     calling: 7 * factfunc( 6 )
factfunc() --> n: 6     calling: 6 * factfunc( 5 )
factfunc() --> n: 5     calling: 5 * factfunc( 4 )
factfunc() --> n: 4     calling: 4 * factfunc( 3 )
factfunc() --> n: 3     calling: 3 * factfunc( 2 )
factfunc() --> n: 2     calling: 2 * factfunc( 1 )
factfunc() --> n: 1     returning 1


main() --> Factorial of 15 is 2004310016

[Ganado]

More accurate would be to say "Factorial of 15 (mod 2^32)".
But maybe I'm just making it more confusing.

________________________

I'll give another way to think about the recursion.
Esso, I know you said you weren't good at mathematics, but bear me with me because it's just some multiplication.

5! = 5 * 4 * 3 * 2 * 1, right?
4! = 4 * 3 * 2 * 1.
But you can see that to calculate 5!, you need to calculate 4!.
In other words,
5! = 5 * (4!) = 5 * (4 * 3 * 2 * 1).

This can be generalized to n! = n * (n - 1)! (for positive n).

But look, now the definition of factorial... contains a factorial. There is where the recursion comes in.

In pseudo-code, we could write this as:
factorial(n) = n * factorial(n-1)

Or, in C++,

int factorial(int n)
{
    return n * factorial(n-1);
}

The above is almost correct, except that what will happen is, n = 5, then you'd call factorial(4), factorial(3), factorial(2), factorial(1), factorial(0), factorial(-1), etc.
The problem is there's no ending condition, so it will recurse forever.

This can be stopped by having a terminating condition for the recursion.

int factorial(int n)
{
    if (n <= 1)
        return 1; // don't recurse anymore. We're done.
    else
        return n * factorial(n-1);
}

And that's how your code is made (although flip the if statements).

[jonnin]

Guys ... I was trying to figure it out
how does this statement (else return 1;)
doesn't make the condition passes through it and give the whole function the value (1) at the end of time,

well, it does! the function, WHEN THE PARAMETER IS 1, RETURNS 1. The whole value of the function, in that call, is one, yes. What you are not seeming to get is that the function is called many times. In some of the calls, it is NOT called with 1, and it returns a different number.

again, in reverse, its called with 1. it returns 1. That resumes the call when it was 2, so it takes the value 1, multiples it by 2, and returns 2. The two returns to when it was called with 3, multiples 3*2, and returns 6. and so on until it backs all the way up to the original call (5 in my examples).

the function calls of recursion are distinct.
its as if you said
for(x = 1; x <=5; x++)
y *= foo(x);//foo is called several times in this loop. the result of foo(1) has not effect on the result of foo(5), right? Recursion is the same way. The fact that it happens to call itself is irrelevant, each call is still independent.

Upper level math does touch recursive definitions of some series and the like, but more or less recursion is not a math thing. Its doing math here, but you could just as easily reverse a string with it (recursion is good at reversing things, note how it is multiply in reverse in your factorial).

char cs[] = "hello world";
void rev(char* c)
{
    if(*c) rev(c+1);
     cout << *c;
}

is the letter the 0 terminating letter of a c-string? nope, its h. call it with e. is e the 0? nope, call it with l, l, 0, space, w, o, r, l,d, there is is, cout the 0 null char (which will look like a space in a console window, this is a quick lazy example so ignore that), cout the d,l,r,o,w,space,o,l,l,e,h …

it takes a little time to really 'get' recursion. Once you see it, you will be fine. It lets you write small functions that do things cleanly with a tiny bit of code that otherwise take much more code, so keep it in your toolbox. Also, think before you do: a factorial in a real piece of code would use a lookup table, not a computation. Its used to teach recursion because it is a simple example.
int fact[] = {1,1,2,6,24,120,720, ...};
..
result = fact[5]; //120

[Esso]

I guess I got it right now, I just try to
understand every single tiny peace of code how does it work
as best as I can, cause I have a fish memory
so I find my self have to understand rather
try to memorize the abstract formula with no sense, however it is very useful to memorize
pre-made forms as well....I believe that you guys have done a very great job to make it as close as possible to me I really appreciate it a lot!
I also wanted to share this with you:
https://www.cs.usfca.edu/~galles/visualization/RecFact.html