Recursion in c++ Factorial Program

Source: Image is taken from: IBM Developers website

Just take a look at the picture above, you will understand it better. The number never gets stored, but gets called recursively to calculate the output.

So when you call the fact(4) the current stack is used to store every parameter as the recursive calls occur down to factorialfinder(1). So the calculation goes like this: 5*4*3*2*1.

int factorialfinder(int x)         
{
    if (x == 1)        // HERE 5 is not equal to 1 so goes to else
    {
        return 1;
    }else
    {
        return x*factorialfinder(x-1); // returns 5*4*3*2*1  when x==1 it returns 1
    }
}

Hope this helps.

Return 1 is not returning the actual answer. It's just returning the answer to calling

factorialfinder(1);

which happens in your code.

In any program, a call stack is a space in memory that is used to keep track of function calls. Space from this memory is used to store the arguments to a function, as well as the return value of that function. Whenever some function A calls another function B, A gets the return value of B from that space.

A recursive function is nothing special, it's just an ordinary function calling another function (that happens to be itself). So really, when a recursive function F calls itself, it's calling another function: F calls F', which calls F'', which calls F''', etc. It's just that F, F'', F''' etc. execute the same code, just with different inputs.

The expression if (x == 1) is there to check when this process should be stopped. The return value of F''' is used by F''. The return value of F'' is used by F'. The return value of F' is used by F.

In Factorial of some number, the operation is (n) * (n-1) * (n-2) * .... * (1). I've highlighted the 1; this is the condition that's being checked.

A recursive function breaks a big problem down into smaller cases.

Going over your program:

call factorialfinder with 5, result is stored as 5 * factorialfinder(4)

call factorialfinder with 4, result is stored as 5 * 4 * factorialfinder(3)

call factorialfinder with 3, result is stored as 5 * 4 * 3 * factorialfinder(2)

call factorialfinder with 2, result is stored as 5 * 4 * 3 * 2 * factorialfinder(1)

call factorialfinder with 1, result is stored as 5 * 4 * 3 * 2 * 1

in essence it combines the result of a stack of calls to factorialfinder until you hit your base case, in this case x = 1.

Well, the factorial function can be written using recursion or not, but the main consideration in the recursion is that this one uses the system stack, so, each call to the function is a item in the system stack, like this (read from the bottom to the top):

Other consideration in the recursion function is that this one has two main code piece:

1. The base case
2. The recursion case

In the base case, the recursive function returns the element that bounds the algorithm, and that stop the recursion. In the factorial this element is 1, because mathematically the factorial of number one is 1 by definition. For other numbers you don't know the factorial, because of that, you have to compute by using the formula, and one implementation of it is using recursion, so the recursive case.

Example: The factorial of 5, the procedure is: 5*4*3*2*1 = 120, note you have to multiply each number from the top value until number 1, in other words, until the base case takes place which is the case that you already knew.