Factorial using Recursion in Java

Question

I am learning Java using the book Java  The Complete Reference  Currently I am working on the topic Recursion   Please Note  There are similar questions on stackoverflow  I searched them but I didn t find the solution to my question  I am confused with the logic in the following program   If I run the below program  it produces the correct output  but I didn t understand the logic    I didn t understand the logic in the following line   result   fact n-1    n  From my knowledge  If we pass the value of n 4 as shown in the below program   Then  3   4 is stored in the result i e   12   Again  fact n-1  is called  Then n becomes 3  Then the 2   3 is stored in the result replacing the previous 12  I think you understood where I am stuck up confused  Thank you     class Calculation       int fact int n                int result          if n  1           return 1          result   fact n-1    n         return result           public class Factorial        public static void main String args                  Calculation obj one   new Calculation            int a   obj one fact 4          System out println  The factorial of the number is       a

User · Answer

What happens is that the recursive call itself results in further recursive behaviour  If you were to write it out you get    fact 4   fact 3    4    fact 2    3    4     fact 1    2    3    4     1   2    3    4

User · Answer

In my opinion  and that being the opinion of someone with beginner level knowledge of java  I would suggest that the n    1 to be changed to n  lt   1 or  n    0    n  1  because the factorial of 0 is 1

User · Answer

The correct one is    int factorial int n        if n  0  n  1          return 1      else          return n factorial n-1       This would return 1 for factorial 0  Do it believe me   I have learned this the hard way  Just for not keeping the condition for 0 could not clear an interview

User · Answer

Your confusion  I believe  comes from the fact that you think there is only one result variable  whereas actually there is a result variable for each function call  Therefor  old results aren t replaced  but returned   TO ELABORATE   int fact int n        int result      if n  1       return 1      result   fact n-1    n     return result      Assume a call to fact 2    int result  if   n    1      false  go to next statement result   fact 1    2     calls fact 1          fact 1       int result     different variable      if   n    1       true          return 1      this will return 1  i e  call to fact 1  is 1 result   1   2     because fact 1    1 return 2    Hope it s clearer now

User · Answer

To understand it you have to declare the method in the simplest way possible and martynas nailed it on May 6th post   int fact int n        if n  0  return 1      else return n   fact n-1       read the above implementation and you will understand

User · Answer

import java util Scanner   public class Factorial       public static void main String   args            Scanner keyboard   new Scanner System in           int n           System out println  Enter number              n   keyboard nextInt            int number   calculatefactorial n           System out println  Factorial     number             public static int calculatefactorial int n           int factorialnumbers 1          while n gt 0            factorialnumbers  int  factorialnumbers n--                        return factorialnumbers

User · Answer

public class Factorial        public static void main String   args            System out println factorial 4               private static long factorial int i             if i lt 0   throw new IllegalArgumentException  x must be  gt   0             return i  0  i  1  1 i factorial i-1

User · Answer

Using Java 8 and above  using recursion itself    UnaryOperator lt Long gt  fact   num - gt  num lt 1   1   num   this fact apply num-1     And use it like    fact apply 5      prints 120   Internally it calculate like  5  4  3  2  1  1

User · Answer

Well variable  result  is a local variable  When fact   method is called from  main  method variable  result  is stored in different variable   Also line   result   fact n-1    n     here logic is finding factorial using recursion  Recursion in java is a procedure in which a method calls itself   Meanwhile you can refer this resource on factorial of a number using recursion

User · Answer

Although this is old  it still keeps coming up pretty well in google  So I figured I d mention this  No one mentioned to check for when x   0    0  and 1  both   1    This isn t being checked with the previous answers  and would cause a stack overflow  if fact 0  was run  Anyway simple fix   public static int fact int x       if  x  1   x  0          return 1      return fact x-1    x      fact

User · Answer

A recursive solution using ternary operators   public static int fac int n        return  n  lt  1    1   n fac n-1

User · Answer

First you should understand how factorial works   Lets take 4  as an example   4    4   3   2   1   24   Let us simulate the code using the example above   int fact int n                int result         if n  0    n  1           return 1          result   fact n-1    n         return result          In most programming language  we have what we call function stack  It is just like a deck of cards  where each card is placed above the other--and each card may be thought of as a function So  passing on method fact   Stack level 1  fact 4     n   4 and is not equal to 1  So we call fact n-1  n   Stack level 2  fact 3    Stack level 3  fact 2   Stack level 4  fact 1     now  n   1  so we return 1 from this function   returning values     Stack level 3  2   fact 1    2   1   2  Stack level 2  3   fact 2    3   2   6  Stack level 1  4   fact 3    4   6   24  so we got 24   Take note of these lines   result   fact n-1    n             return result    or simply   return fact n-1    n    This calls the function itself  Using 4 as an example   In sequence according to function stacks    return fact 3    4  return fact 2    3   4 return fact 1    2   3   4   Substituting results     return 1   2   3   4   return 24   I hope you get the point

User · Answer

public class Factorial2       public static long factorial long x            if  x  lt  0               throw new IllegalArgumentException  x must be  gt   0            if  x  lt   1               return 1      Stop recursing here         else             return x   factorial x-1       Recurse by calling ourselves

User · Answer

public class Factorial   public static void main String   args       int n   7     int result   1     for  int i   1  i  lt   n  i             result   result   i          System out println  The factorial of 7 is     result

User · Answer

The key point that you missing here is that the variable  result  is a stack variable  and as such it does not get  replaced   To elaborate  every time fact is called  a NEW variable called  result  is created internally in the interpreter and linked to that invocation of the methods  This is in contrast of object fields which linked to the instance of the object and not a specific method call

User · Answer

IMHO  the key for understanding recursion-related actions is    First  we dive into stack recursively  and with every call we somehow modify a value  e g  n-1 in func n-1    which determines whether the recursion should go deeper and deeper  Once recursionStopCondition is met  e g  n    0   the recursions stops  and methods do actual work and return values to the caller method in upper stacks  thus bubbling to the top of the stack  It is important to catch the value returned from deeper stack  somehow modify it  multiplying by n in your case   and then return this modified value topwards the stack  The common mistake is that the value from the deepest stack frame is returned straight to the top of the stack  so that all method invocations are ignored    Surely  methods can do useful work before they dive into recursion  from the top to the bottom of the stack   or on the way back

User · Answer

Here is yet another explanation of how the factorial calculation using recursion works   Let s modify source code slightly   int factorial int n          if  n  lt   1              return 1        else             return n   factorial n - 1       Here is calculation of 3  in details     Source  RECURSION  Java  C       Algorithms and Data Structures

User · Answer

result is a local variable of the fact method  So each time the fact method is called  the result is stored in a different variable than the previous fact invocation   So when fact is invoked with 3 as argument  you can imagine that its result is   result3   fact 2    3  result3   result2   3  result3   1   2   3

[java] Factorial using Recursion in Java

Examples related to java

Examples related to recursion