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
    5

    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
    5

    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
    5

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
  •