Factorial problem giving wrong output in c++

Question

Trying to write factorial problem for my classwork but getting wrong output. Don't understand what am I doing wrong. Here is my code.

int fact(int number) {
    if(number == 0) {
           return 1;
        }
     return  fact_i(number, 1);
}

int fact_i(int curNumber, int sum) {
    if(curNumber == 1) {
        return sum;
    } else {
        return fact_i(curNumber - 1, sum);
    }
}

Doesn't look like you are doing anything to update `sum` That's odd for a recursive function, so I'd start investigating there. It might turn out that you simply don't need to pass it, but it could be important. — user4581301, Oct 08 '18 at 06:09
Why I'm getting constantly down vote, while I'm sharing my problem here. Or it is the wrong place for sharing programming problem? — S M Sajjad Salam, Oct 08 '18 at 06:46
@SMSajjadSalam it's because you didn't use search or you'd found answer to your question over than once, and problem looked like a typo. E.g. search `factorial recursion [c++]` This case is simple enough, but usually you're required to post complete minimal example. — Swift - Friday Pie, Oct 08 '18 at 06:53
@SMSajjadSalam, probably because people think you should spend a bit of time stepping through your code with a debugger before posting such trivial questions. You totally should. — Jan Hudec, Oct 08 '18 at 06:54
This is the right place for a programming problem. Unfortunately your problem is fairly trivial and could have been pin-pointed with a debugger or some debug statements to track the state of the program. You'll probably find the debugger a bit easier. Good reading here: [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). Others may have downvoted because you did not provide a [mcve], but I consider that one a bit iffy since all of the information needed to spot the errors is in the post. — user4581301, Oct 08 '18 at 06:57
So as of comments I should mention how long I spent time in finding out the problem and only expert in stackoverflow can question here? Newbies or not encouraged here? — S M Sajjad Salam, Oct 08 '18 at 06:59
@SMSajjadSalam In my opinion, the only thing wrong with the question is that there's no mention of what the wrong output *is* (and that's no reason to downvote). Don't be discouraged by downvotes - we all get them, and sometimes for no apparent reason. — molbdnilo, Oct 08 '18 at 07:05
It's not so much the time that you spent as much as how you spent it. Some debugging techniques, (step through code with debugger) can be extremely fast. Others (crafting a MCVE) can be quite slow. Different bugs are more vulnerable to different attacks. no one writes perfect code. Donald Knuth, possibly THE expert programmer once wrote, "Beware of bugs in the above code; I have only proved it correct, not tried it." Because of this, debugging is an utterly vital skill to the working programmer, and the only way to get good at it is through practice. — user4581301, Oct 08 '18 at 07:12
@molbdnilo no one asked for the wrong output, and factorial output are fixed. — S M Sajjad Salam, Oct 08 '18 at 07:14
@SMSajjadSalam "The output is wrong" is not a good problem description, as it could mean anything and leaves other people to figure it out. The code you posted also doesn't output anything, so the problem could be in the rest of your code for all the rest of the world knows. "My factorial function always returns 1" would be far better. It's not only a question of manners - a good problem description will also get you better answers faster. — molbdnilo, Oct 08 '18 at 07:28
@SMSajjadSalam downvotes (for sometimes no apparent reason) can be quite a problem at first, nearly everyone had to go through the stage of learning how and when to write a question on SO. You can however eliminate a lot of the possible downvotes if you research the topic a bit. Just read a bit through the [Helpcenter](https://stackoverflow.com/help/how-to-ask) and http://idownvotedbecau.se/ this helped me to avoid basically 99% of downvotes I was getting and understand why I was getting them. — Robin B, Oct 08 '18 at 07:31

Jan Hudec · Answer 1 · 2018-10-08T06:33:01.447

You never multiply the sum by the number, so it can't become more than one. The recursion should be:
```
return fact_i(curNumber - 1, curNumber * sum);
```
Note that aiming at the tail call optimization is pointless in this case. While C++ compilers generall can do it (Which, if any, C++ compilers do tail-recursion optimization?), you can't rely on it, because it is not specified, and you'll overflow int way before you might hit any stack limit anyway.

R Sahu · Answer 2 · 2018-10-08T06:30:16.777

The Problem

The error is in the line

return fact_i(curNumber - 1, sum);

It needs to be:

return curNumber*fact_i(curNumber - 1, sum);

Without that, the result never gets accumulated. You just keep on passing 1 up the chain of recursive calls.

Further cleanup

You are using the two terminating conditions -- one if fact and another in fact_i. You can use just one terminating condition to simplify your code.

int fact_i(int curNumber, int sum) {
    if(curNumber == 1) {
        return sum;
    }

    // No need for an else here.
    return fact_i(curNumber - 1, (curNumber-1)*sum);
}

int fact(int number) {
   return  fact_i(number, number);
}

Almost. That way the `sum` is useless. – Jan Hudec Oct 08 '18 at 06:24 — Jan Hudec, Oct 08 '18 at 06:24

score 0 · Answer 3 · answered Oct 08 '18 at 06:34

The proper way to do a tail-recursive factorial is this:

int fact(int number) {
    if(number == 0) {
           return 1;
        }
     return  fact_i(number, 1);
}

int fact_i(int curNumber, int sum) {
    if(curNumber == 1) {
        return sum;
    } else {
        return fact_i(curNumber - 1, sum*curNumber);
    }
}

You have missed the curNumber multiplying with sum in the line return fact_i(curNumber - 1, sum);

Factorial problem giving wrong output in c++

3 Answers3

The Problem

Further cleanup