Results 1 to 6 of 6
  1. #1
    luke is offline Member
    Join Date
    Sep 2010
    Posts
    62
    Rep Power
    0

    Question Again recursion question

    Java Code:
    public class Neper_number {
    	
    static double factorial( int n ) {
    
    		double result;
    
    		if( n <= 0 )
    			return 1;
    		else {
                            result = 1 + (n * factorial(n - 1));
    			return result;
    		}
    }
    }
    I am trying to do recursion in order to solve a problem. Since my original code is not working correctly (I am not doing the recursion correctly) I decided to do recursion but for a simple problem in order to understand what exactly is going on.
    With the above code I thought that for example if I input n = 2 I would get
    result = 1 + 2! = 3; if n = 3 I would get result 1 + 3! = 1 + 3x2x1 = 7 and so on. But instead when I input n = 2 I am getting result = 5, when n = 3 I am getting result = 16 etc.
    Does anybody know why that is?

  2. #2
    Zack's Avatar
    Zack is offline Senior Member
    Join Date
    Jun 2010
    Location
    Destiny Islands
    Posts
    692
    Rep Power
    10

    Default

    Java Code:
    result = [color=red]1 + [/color](n * factorial(n - 1));
    Don't add 1 here.

  3. #3
    luke is offline Member
    Join Date
    Sep 2010
    Posts
    62
    Rep Power
    0

    Default

    Quote Originally Posted by Zack View Post
    Java Code:
    result = [color=red]1 + [/color](n * factorial(n - 1));
    Don't add 1 here.
    I need to add it. I thought that since
    Java Code:
    result = n * factorial(n - 1);
    gives me result = n! (factorial)

    Java Code:
    result = [color=red]1 + [/color](n * factorial(n - 1));
    would give me result = 1 + n! but it's not. Why?

  4. #4
    Zack's Avatar
    Zack is offline Senior Member
    Join Date
    Jun 2010
    Location
    Destiny Islands
    Posts
    692
    Rep Power
    10

    Default

    Firstly, factorial never adds. 7! is 5040, not 5041. 3! is 6, not 7.

    If you want the result of 1+!n, you cannot add it in that location because it's recursive (it will repeat this action as well as the others).

    Work it out step-by-step using 4 as a value:
    Java Code:
    factorial(4) -> result = 1 + (4 * factorial(3))
    factorial(3) -> result = 1 + (3 * factorial(2))
    factorial(2) -> result = 1 + (2 * factorial(1))
    factorial(1) -> result = 1 + (1 * factorial(0))
    factorial(0) -> return 1;
    Java Code:
    Simplified, that's:
    factorial(4) = 1 + (4 * (1 + 3 * (1 + 2 * (1 + (1 * 1)))));
    factorial(4) = 1 + (4 * (1 + 3 * (1 + 2 * (1 + 1))));
    factorial(4) = 1 + (4 * (1 + 3 * (1 + 2 * 2)));
    factorial(4) = 1 + (4 * (1 + 3 * (1 + 4)));
    factorial(4) = 1 + (4 * (1 + 3 * 5));
    factorial(4) = 1 + (4 * 16);
    factorial(4) = 1 + 64;
    factorial(4) = 65; // Should be 1+4! == 1 + 4*3*2*1 == 1 + 24 == 25
    See how the "1 +" recurs over and over? That's where the problem is. Instead of doing that, you'd want something like:
    Java Code:
    public static double FactorialPlusOne(int n) {
        return 1 + factorial(n);
    }
    Since this is not recursive, 1 will only be added once.

  5. #5
    luke is offline Member
    Join Date
    Sep 2010
    Posts
    62
    Rep Power
    0

    Default

    Quote Originally Posted by Zack View Post
    Firstly, factorial never adds. 7! is 5040, not 5041. 3! is 6, not 7.

    If you want the result of 1+!n, you cannot add it in that location because it's recursive (it will repeat this action as well as the others).

    Work it out step-by-step using 4 as a value:
    Java Code:
    factorial(4) -> result = 1 + (4 * factorial(3))
    factorial(3) -> result = 1 + (3 * factorial(2))
    factorial(2) -> result = 1 + (2 * factorial(1))
    factorial(1) -> result = 1 + (1 * factorial(0))
    factorial(0) -> return 1;
    Java Code:
    Simplified, that's:
    factorial(4) = 1 + (4 * (1 + 3 * (1 + 2 * (1 + (1 * 1)))));
    factorial(4) = 1 + (4 * (1 + 3 * (1 + 2 * (1 + 1))));
    factorial(4) = 1 + (4 * (1 + 3 * (1 + 2 * 2)));
    factorial(4) = 1 + (4 * (1 + 3 * (1 + 4)));
    factorial(4) = 1 + (4 * (1 + 3 * 5));
    factorial(4) = 1 + (4 * 16);
    factorial(4) = 1 + 64;
    factorial(4) = 65; // Should be 1+4! == 1 + 4*3*2*1 == 1 + 24 == 25
    See how the "1 +" recurs over and over? That's where the problem is. Instead of doing that, you'd want something like:
    Java Code:
    public static double FactorialPlusOne(int n) {
        return 1 + factorial(n);
    }
    Since this is not recursive, 1 will only be added once.
    Thanks a lot for the help, Zack. I got it.
    Now I have to try to do the more complicated recursion. I want to try it myself before asking you :)
    By the way how can I change the status of a post to [SOLVED] ?

  6. #6
    Zack's Avatar
    Zack is offline Senior Member
    Join Date
    Jun 2010
    Location
    Destiny Islands
    Posts
    692
    Rep Power
    10

Similar Threads

  1. Recursion question
    By luke in forum New To Java
    Replies: 12
    Last Post: 10-04-2010, 10:04 PM
  2. Touch recursion question
    By myst in forum New To Java
    Replies: 18
    Last Post: 06-08-2010, 06:48 PM
  3. very simple Question
    By arsenal4ever_11 in forum NetBeans
    Replies: 2
    Last Post: 05-27-2010, 08:51 PM
  4. some simple question?
    By jperson in forum New To Java
    Replies: 4
    Last Post: 05-03-2010, 05:32 PM
  5. Simple Question
    By barusk in forum Networking
    Replies: 13
    Last Post: 03-04-2009, 07:33 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •