Recursion in C++ Factorial Program

Recursive function for finding factorial of a number

Your program suffers from undefined behavior.

In the first call to factorial(5), where you have

return number * factorial(--number);

you imagine that this is going to compute

       5      * factorial(4);

But that's not guaranteed!

What if the compiler looks at it in a different order?

What it if works on the right-hand side first?

What if it first does the equivalent of:

temporary_result = factorial(--number);

and then does the multiplication:

return number * temporary_result;

If the compiler does it in that order, then temporary_result will be factorial(4), and it'll return 4 times that, which won't be 5!. Basically, if the compiler does it in that order -- and it might! -- then number gets decremented "too soon".

You might not have imagined that the compiler could do things this way.

You might have imagined that the expression would always be "parsed left to right".

But those imaginations are not correct.

(See also this answer for more discussion on order of evaluation.)

I said that the expression causes "undefined behavior", and this expression is a classic example. What makes this expression undefined is that there's a little too much going on inside it.

The problem with the expression

return number * factorial(--number);

is that the variable number is having its value used within it, and that same variable number is also being modified within it. And this pattern is, basically, poison.

Let's label the two spots where number appears, so that we can talk about them very clearly:

return number * factorial(--number);
       /* A */             /* B */

At spot A we take the value of the variable number.

At spot B we modify the value of the variable number.

But the question is, at spot A, do we get the "old" or the "new" value of number?

Do we get it before or after spot B has modified it?

And the answer, as I already said, is: we don't know. There is no rule in C to tell us.

Again, you might have thought there was a rule about left-to-right evaluation, but there isn't. Because there's no rule that says how an expression like this should be parsed, a compiler can do anything it wants. It can parse it the "right" way, or the "wrong" way, or it can do something even more bizarre and unexpected. (And, really, there's no "right" or "wrong" way to parse an undefined expression like this in the first place.)

The solution to this problem is: Don't do that!

Don't write expressions where one variable (like number) is both used and modified.

In this case, as you've already discovered, there's a simple fix:

return number * factorial(number - 1);

Now, we're not actually trying to modify the value of the variable number (as the expression --number did), we're just subtracting 1 from it before passing the smaller value off to the recursive call.
So now, we're not breaking the rule, we're not using and modifying number in the same expression.
We're just using its value twice, and that's fine.

For more (much more!) on the subject of undefined behavior in expressions like these, see Why are these constructs using pre and post-increment undefined behavior?

Recursive factorial function program returns 0 for large number input in C

If you print the values in hex, what is happening becomes more apparent:

Factorial(0) = 0000000000000001
Factorial(1) = 0000000000000001
Factorial(2) = 0000000000000002
Factorial(3) = 0000000000000006
Factorial(4) = 0000000000000018
Factorial(5) = 0000000000000078
Factorial(6) = 00000000000002d0
Factorial(7) = 00000000000013b0
Factorial(8) = 0000000000009d80
Factorial(9) = 0000000000058980
Factorial(10) = 0000000000375f00
Factorial(11) = 0000000002611500
Factorial(12) = 000000001c8cfc00
Factorial(13) = 000000017328cc00
Factorial(14) = 000000144c3b2800
Factorial(15) = 0000013077775800
Factorial(16) = 0000130777758000
Factorial(17) = 0001437eeecd8000
Factorial(18) = 0016beecca730000
Factorial(19) = 01b02b9306890000
Factorial(20) = 21c3677c82b40000
Factorial(21) = c5077d36b8c40000
Factorial(22) = eea4c2b3e0d80000
Factorial(23) = 70cd7e2933680000
Factorial(24) = 9343d3dcd1c00000
Factorial(25) = 619fb0907bc00000
Factorial(26) = ea37eeac91800000
Factorial(27) = b3e62c3358800000
Factorial(28) = ad2cd59dae000000
Factorial(29) = 9e1432dcb6000000
Factorial(30) = 865df5dd54000000
Factorial(31) = 4560c5cd2c000000
Factorial(32) = ac18b9a580000000
Factorial(33) = 2f2fee5580000000
Factorial(34) = 445da75b00000000
Factorial(35) = 58cde17100000000
Factorial(36) = 7cf3b3e400000000
Factorial(37) = 0f38fff400000000
Factorial(38) = 4275fe3800000000
Factorial(39) = 1ff9ba8800000000
Factorial(40) = ff05254000000000
Factorial(41) = d7d2f74000000000
Factorial(42) = 689c908000000000
Factorial(43) = 924c458000000000
Factorial(44) = 251bf20000000000
Factorial(45) = 85e98a0000000000
Factorial(46) = 0ff6cc0000000000
Factorial(47) = ee4f740000000000
Factorial(48) = aee5c00000000000
Factorial(49) = 79f9c00000000000
Factorial(50) = d2c7800000000000
Factorial(51) = fdbe800000000000
Factorial(52) = 8ab2000000000000
Factorial(53) = b6da000000000000
Factorial(54) = 91fc000000000000
Factorial(55) = 5d24000000000000
Factorial(56) = 5fe0000000000000
Factorial(57) = 58e0000000000000
Factorial(58) = 22c0000000000000
Factorial(59) = 0240000000000000
Factorial(60) = 8700000000000000
Factorial(61) = 2b00000000000000
Factorial(62) = 6a00000000000000
Factorial(63) = 1600000000000000
Factorial(64) = 8000000000000000
Factorial(65) = 8000000000000000

As you continue to multiply in values containing 2 as a factor, the number of trailing zeros continues to increase. By the time you multiply in 66, all nonzero bits have been pushed out to the left, so you're left with 0.

Also, the values from 21! to 65! are not actually random values but the low order 64 bits of the result. Unsigned integer arithmetic is carried out modulo 2^bitlen where "bitlen" is the bit length of the type in question which is 64 in this case.

Why this recursive factorial program only returns the number that I want to calculate?

.global main

main:
    mov r0,#5    // 5 is the number that I want to calculate the factorial
    mov r1,r0

factorial:
    cmp r1,#1
    beq end
    sub r1,r1,#1    // n-1
    push {ip,lr}    // save the lr
    bl factorial
    mul r0,r1,r0    // multiply r0 * n-1
    pop {ip,lr}
end:
    bx  lr

walk through your code...

mov r0,#5  r0 = 5
mov r1,r0  r1 = 5
cmp r1,#1
beq end 
sub r1,r1,#1  r1 = 4
push
bl factorial
cmp r1,#1
beq end
sub r1,r1,#1 r1 = 3

do you see the problem yet? you should already see it by now.

and this continues a few more times until
sub r1,r1,#1 r1 = 1
push
bl factorial
cmp r1,#1
beq end
bx lr
mul r0,r1,r0   r0 = 1 * 5 = 5
pop
bx lr
cmp r1,#1
beq end
bx lr
mul r0,r1,r0   r0 = 1 * 5 = 5
...

try it without recursion first, and remember for recursion, you will need a local variable that changes for each call in this case and you need to think about where you are placing the comparison if you want to use a single value or if you want to use two, The ip in the push is just to keep the stack aligned so remember that as you can use that to save one of these registers and restore it on the way out.

Note that from gradeschool

4*3*2*1 = 1*2*3*4

You need to put some effort in before asking a question at stackoverflow.

Write and debug it in C first (or some language you are stronger in), litter the code with printfs, once you have the algorithm in a language you know then simply re-write it in assembly language or whatever new language you are learning.

recursive factorial function that prints to console on it's own (C#)

You could use a local function as the actual recursive part, using the outer Factorial function as a wrapper which just calls it!

int Factorial(int number)
{
    static int DoFactorial(int number) => number <= 1
        ? 1
        : number *= DoFactorial(number - 1);
        
    var answer = DoFactorial(number);
    Console.WriteLine(answer);
    
    return answer;
}