• Post Reply Bookmark Topic Watch Topic
  • New Topic

Having some trouble understanding some recursive codes of Factorial  RSS feed

 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, everyone

It was quite recently that Data Structures was introduced to me, so I started out writing some iterative programs recursively.I found some strange output which shouldn't have come out but if you take a look at these three codes




These are three versions of the code, achieving the same objective of obtaining a given number and returning the factorial, but in spite of the changes made to the code, they produce the same result. I needed a reason as to why it is so? I tried to dry run all the codes but at some point or the other I got confused, and had to start all over again and couldn't come up with a proper result. Any help would be appreciated!

Regards,
Ranajoy Saha
 
Tim Cooke
Marshal
Posts: 4041
239
Clojure IntelliJ IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Neither of them compile for me because "result" is not defined.

There is no need to have any state in the factorial function, which means you don't need the "result" variable at all. Have a think and see if you can simplify your function to not need any variables.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tim Cooke wrote:Neither of them compile for me because "result" is not defined.

There is no need to have any state in the factorial function, which means you don't need the "result" variable at all. Have a think and see if you can simplify your function to not need any variables.

I'm sorry! I forgot to mention that the "result" variable will be declared and initialized as 1 in scope of the class. I am using the result variable, to abide by the Java convention that a function should have only one return statement and that too at the end! The code below should compile!

 
Campbell Ritchie
Marshal
Posts: 56534
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You know you can shorten those methods greatly? You can use the ?: operator to reduce them to one line.
I would use zero as a base case rather than 1, because 0 has a factorial which is 1.

I would also suggest that they are functions and in the most dubious classification of methods ever seen they all come out as 1368 (except the main method), so they should be considered candidates to be marked static.

I don't think you should use *=. I don't think it will work.
Don't make result a field. If you are using recursion you are straying into the realms of functional programming and a function should not alter fields or have any other such side‑effects.
If you are going to use recursion call the same method, so in fectorial3 call factorial3 not factorial. Also you can get rid of the local variables in the main method:-
System.out.println("z = " + obj.factorial3(5));

Is there actually a difference between the factorial method and factorial2?

You are displaying the correct answer from all three calls, but if you wrote ..."z = " + z... instead of + x things might become interesting
 
Dave Tolls
Ranch Foreman
Posts: 3056
37
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
I don't think you should use *=. I don't think it will work.


It does work, but it is pointless.
At least if I'm interpreting the byte code correctly.
The value of result is put to one side, then the factorial call is made, and when it returns from that then the *= is done.
So result is always 1, for each and every call.
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:You know you can shorten those methods greatly? You can use the ?: operator to reduce them to one line.
I would use zero as a base case rather than 1, because 0 has a factorial which is 1.

I would also suggest that they are functions and in the most dubious classification of methods ever seen they all come out as 1368 (except the main method), so they should be considered candidates to be marked static.

I don't think you should use *=. I don't think it will work.
Don't make result a field. If you are using recursion you are straying into the realms of functional programming and a function should not alter fields or have any other such side‑effects.
If you are going to use recursion call the same method, so in fectorial3 call factorial3 not factorial. Also you can get rid of the local variables in the main method:-
System.out.println("z = " + obj.factorial3(5));

Is there actually a difference between the factorial method and factorial2?

You are displaying the correct answer from all three calls, but if you wrote ..."z = " + z... instead of + x things might become interesting


I'm really sorry! While printing the results, I wrote the print statement for the x variable and then copied the entire things and forgot to change the variable that is to be printed! The answer to z came out be the square of the factorial of 5, but when I commented all of the x, y variables, the out put came out as 120, I don't know, what is going on with my code. I saw your post, now I've changed the access modifiers to static. But, I don;t know how to answer your question. "Is there actually a difference between the factorial method and factorial2?" Well, is there. I don't know. I can't figure it out. Is there any difference?

Output : z = 120
Output :
x = 120
y = 120
z = 14400
 
Dave Tolls
Ranch Foreman
Posts: 3056
37
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You never reset "result" between calls, so it's 120 when you go into factorial3.

Also, your factorial2 and factorial3 methods calls factorial(), not themselves.
 
Campbell Ritchie
Marshal
Posts: 56534
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dave Tolls wrote: . . .
So result is always 1, for each and every call.
Not when I tried it, it wasn't
 
Campbell Ritchie
Marshal
Posts: 56534
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ranajoy Saha wrote: . . . I wrote the print statement for the x variable and then copied the entire things . . .
Just as well to make that sort of mistake where it doesn't matter.

I got z=14400 too when I tried your code. Dave Tolls has already explained why you are getting that problem.

Again: get rid of the field. Get rid of the local variables. Simply return the result of the calculation. Write
return 1L;
or
return n * factorial(n - 1L);
As I said before you can reduce that to one line with the ?: operator. Look in the old Sun style guide §10.5.2.
I would prefer (n == 0L) as a base case. Remember the factorial of 0 is 1.
Because you are working with long arithmetic, you should append the L to your number literals. And make sure it is L not l for reasons explained in the Java® Language Specification.
 
Dave Tolls
Ranch Foreman
Posts: 3056
37
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Dave Tolls wrote: . . .
So result is always 1, for each and every call.
Not when I tried it, it wasn't


If done using only factorial3 (so not calling the factorial() method) the "result" value used in the += is always 1.
That's why it "works".
Pointless, but works...

And (for laughs) here's some additional logging:


Which results in:
Factorial 3
2
6
24
120
120
Factorial
2
6
24
120
120

In the former each value of "result" from the prior step is overwritten by 1 * n*factorial(n-1).
 
Ranajoy Saha
Ranch Hand
Posts: 105
2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dave Tolls wrote: . . .
And (for laughs) here's some additional logging:
. . .


Thank you Dave Tolls and Campbell Ritchie for helping me out with these problems and giving a clear account describing how to rectify these problems. Thanks a lot!
 
Campbell Ritchie
Marshal
Posts: 56534
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome
Try with those methods being static, and there is no need for any instances of that class. Also you can shorten it as I said with the ?: operator. Note you have now got rid of all the local variables, except the parameter n.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!