What is wrong with the following method for calculating factorials? /** * Calcul
ID: 3864849 • Letter: W
Question
What is wrong with the following method for calculating factorials?
/**
* Calculates the factorial of a non-negative integer, that is, the product of * all integers between 1 and the given integer, inclusive.
* The worstTime(n) is O(n), where n is the given integer.
*
* @param n the non-negative integer whose factorial is calculated. *
* @return the factorial of n. *
* @throws IllegalArgumentException if n is less than 0. *
*/
public static long factorial (int n) {
if (n < 0)
throw new IllegalArgumentException( );
if (n <= 1) return 1;
return fact (n+1) / (n+1); } // fact
Explanation / Answer
The logic you think for this is absolutely correct like to find 5!, you are doing something like (6!) / 6 which is valid.
But from the programming point of view, this is not giving correct answer.
The reason behind this is...
Consider the same example : 5! = 6! / 6
= (7! / 7) / 6
= [ (8!/ 8) / 7 ] / 6
So this goes on and makes an infinite loop as the termination condition for this loop is when n<=1 but that is never going to happen as n is increasing by 1 every time in recursion.
So, to correct this error, applying the logic of recursion but in another way, in the given code, n is incremented every time so never reaches 0 where the function is stopped executing. So, to reach to 0,we will be decrementing n every time. This logic can be understood as:
5! = 5 * 4!
= 5 * 4 * 3!
......
= 5 * 4 * 3 * 2 * 1 * 0!
Here, 0! = 1 is returned and the recursion is completed so the 5! becomes 120.
so, to write this in the code form...
/**
* Calculates the factorial of a non-negative integer, that is, the product of * all integers between 1 and the given integer, inclusive.
* The worstTime(n) is O(n), where n is the given integer.
*
* @param n the non-negative integer whose factorial is calculated. *
* @return the factorial of n. *
* @throws IllegalArgumentException if n is less than 0. *
*/
public static long factorial (int n) {
if (n < 0)
throw new IllegalArgumentException( );
if (n <= 1) return 1;
return n * fact (n-1);
} // fact
This will solve the error of going into the infinite loop. That is the solution you required for this.
Please comment if there is any query. Thank you. :)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.