CODEWITHSUNDEEP
crecursion
Chris Yates
Chris Yates

Reputation: 91

How does return work exactly in Factorial?

I'am getting my head around recursion from the very basics, since I struggled in the past. I'm looking at this Factorial solution:

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

So the function keeps calling itself until n == 0. Then it goes on returning values at each call. Now that's what I don't understand: When it comes back from base condition it returns a value and it keeps adding values from each of the calls.

Where are these values being stored to finally be able to return the total sum?

Upvotes: 0

Views: 556

Answers (3)

chqrlie
chqrlie

Reputation: 144951

As you correctly interpret, the function Factorial calls itself unless the argument is 0. Since it calls itself with n - 1, eventually the sequence of recursive calls will stop after n steps. Each call is a new instance or invocation of the function, the computation is suspended until the new instance returns. The state of a given instance is kept in memory in an area called the stack (on most current environments).

When the final instance called with the value 0 returns, the last calling instance can finish its computation and return 1 * 1 to its caller, and so on until the initial instance can finish its multiplication and return the factorial of its argument.

------- stop reading here unless you are interested in implementation details --------

First problem with the above code, if n is negative or very large, the program will likely invoke undefined behaviour because of too many recursive calls, each consuming some stack space, a limited resource.

Second problem: the int type has a limited range of possible values. On most curent systems, int is stored as 32 bits. Factorials grow very quickly, so Factorial(12) yields 479001600, which causes arithmetic overflow when multiplied by 13 because the result 6227020800 cannot fit in 32 bits. Arithmetic overflow invokes undefined behaviour.

You can try and compile your Factorial function on this site: http://gcc.godbolt.org/# . It has an interactive compiler and shows the assembly code. Try different optimizer options:

  • -m32 -O1 will give a recursive version, not too difficult to understand
  • -m32 -O2 shows that the compiler is astute enough to transform your recursive C implementation to an iterative assembly version, both shorter and faster than the -O1 version.

  • -m32 -O3 yields vastly more complex code, involving SIMD instructions on MMX registers... potentially faster than the -O2 version, but completely over-engineered since a simple small lookup table without a single test would suffice:

    int Factorial(int n) {
    static int f32[16] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320,
                           362880, 3628800, 39916800, 479001600,
                           0, 0, 0 };
    return f32[n & 15];
}

Notice how one can take advantage of undefined behaviour semantics (anything goes) to simplify the implementation and remove tests. Compilers are allowed to do that and some of them do indeed.

Upvotes: 3

Ziezi
Ziezi

Reputation: 6467

Quick answer:

Everything is stored on the stack in the respective activation record1.

Here is a depiction of the function calls (on the left) and of the stack (on the right), of the recursive function implementing factorial: enter image description here

Your function int Factorial(int n); is using recursion. The first return is called base case and it acts as a termination condition and the second return is the recursive step, which results in a call to the same function with one of the parameters (used in the base case if condition statement) modified. The result is accumulated and returned after the base condition is reached.

Here is an excellent explanation of recursion, using exactly factorial as an example.

1. On computer architecture level the result is stored in a specific register, accumulating the final result.

Upvotes: 0

Nitin Tripathi
Nitin Tripathi

Reputation: 1254

To recursively compute its result on a given input, a recursive function calls (a copy of) itself with a different ("smaller" in some way) input and uses the result of this call to construct its result. The recursive call does the same, unless the base case has been reached. Thus a call stack develops in the process. For example, to compute Factorial(3), this recursively calls in turn Factorial(2), Factorial(1), Factorial(0) ("winding up" the stack), at which point recursion terminates with Factorial(0) = 1, and then the stack unwinds in reverse order and the results are calculated on the way back along the call stack to the initial call frame Factorial(3), where the final result is calculated as 3*2 =: 6 and finally returned. In this example a function returns a single value.

Upvotes: 0

Related Questions