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

Of course, the code itself fulfills its intended purpose, and I need to understand its logic of operation. It seems that I understand the work of recursion (and complex recursion) and the work of "return", but something in this example is not so simple. Specifically, what interests me, why without the first "return", which ends the work of "if" and the number that it returns, would this calculation be impossible? I also “stitched” this code in “VS” and it is not clear how this factorial was calculated in general? Because if we write down the values ​​that were calculated, then these were the following expressions:

 5 * 4 = 20 4 * 3 = 12 3 * 2 = 6 2 * 1 = 2 1 * 0 = 0

<- these expressions were shown to me by "VS" when the code was being walked (of course, "VS" did not show them to me in the form in which I wrote them here), that is, the first factor is our "n" second factor is - Factorial (- n) and, accordingly, the product is the product of these factors. And I ask how having such works and multipliers managed to correctly calculate factorial? Yes, I understand that such questions arose in me because of insufficient knowledge of the logic of this whole economy (recursion, the keyword "return", etc.) D, and therefore, in fact, I ask this question. I hope, clearly stated the essence of the problem)

    3 answers 3

    When calling Factorial (5), a stack frame is created. In this stack, the value n of five is stored.
    There is a comparison with zero. Since it is not equal, the transition to the else branch occurs.
    Multiplication is not yet possible, it will be done later.
    Factorial is called with a value of n reduced by one. That is Factorial (4).
    The stack holding the value of 5 continues to exist.

    And everything happens the same way: a new stack frame is created, the value n of four is stored in it.
    Again branch else. Multiplication is still impossible.
    New Challenge Factorial (3).
    The stack holding the value of 4 continues to exist.

    Then call Factorial (2). Then Factorial (1). Stacks continue to exist.

    Finally, call the factororial (0).
    The value of n in the stack is stored again.
    Here the if branch is finally executed. Returns one level higher.
    The current stack with zero is destroyed.

    This is where the multiplication is finally done: 1 * 1. The result comes back higher.
    The stack storing 1 is destroyed.

    This happens to the very top: the returned value is taken, multiplied by the one stored in the current stack frame and passed up.
    The current stack is destroyed.

    When the execution reaches the topmost stack with a value of 5, multiplication and freeing of memory for the stack will also occur. The total value is returned to the calling function.

    • Thank you very much! It is impossible not to understand this explanation. - Albert

    This code calculates the factorial recursion as follows:

     (5 * (4 * (3 * (2 * (1 * (1))))))

    Where parentheses are a separate level of recursion.

      This is simply the condition for exiting the loop (any recursion is just a country-recorded cycle - most optimizers in modern compilers immediately convert them to regular cycles), plus equating 0 to 1 (because 1 * <any number> = <any number>) - if we didn’t equate 0 to 1, then at the end we would multiply everything by 0 and get it .. 0

      For the number "5" in your example it was calculated not what you wrote above, but:

       5 * 4 * 3 * 2 * 1 * 1 = 120

      Here, during return 1 in the first condition, we do not call the Factorial function — at this step the cycle is interrupted.

      If without recursion, the same function will look like this:

       static int Factorial(int n) { int result = 1; for (int i = 1; i <= n; i++) result *= i; // result *= 1; - то самое лишнее умножение на 1. без рекурсии оно нам не нужно return result; }