Results 1 to 6 of 6

Thread: Recursion Help!

  1. #1
    raffs03 is offline Member
    Join Date
    Sep 2012
    Posts
    41
    Rep Power
    0

    Default Recursion Help!

    Java Code:
    // A simple example of recursion.
    class Factorial {
    // this is a recursive method
    int fact(int n) {
    int result;
    if(n==1) return 1;
    result = fact(n-1) * n;
    return result;
    }
    }
    class Recursion {
    public static void main(String args[]) {
    Factorial f = new Factorial();
    System.out.println("Factorial of 3 is " + f.fact(3));
    System.out.println("Factorial of 4 is " + f.fact(4));
    System.out.println("Factorial of 5 is " + f.fact(5));
    }
    Output:
    Java Code:
    Factorial of 3 is 6
    Factorial of 4 is 24
    Factorial of 5 is 120
    The book calls it a recursion/recursive the process of defining something in terms of itself.
    But i can't understand this recursion and i want to learn it because it will be vital in my programming skills.
    Can someone explain to me what's going on to this code?

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default Re: Recursion Help!

    Please edit your post first and give your code regular and consistent indentation. It's very hard to understand code that is poorly formatted, especially when it is someone else's code.

  3. #3
    AndrewM16921 is offline Senior Member
    Join Date
    Jan 2009
    Location
    CA, USA
    Posts
    264
    Rep Power
    6

    Default Re: Recursion Help!

    Quote Originally Posted by Fubarable View Post
    Please edit your post first and give your code regular and consistent indentation. It's very hard to understand code that is poorly formatted, especially when it is someone else's code.
    It's relatively short and not hard to understand at all... that being said, the code tags on this forum are not always forgiving with indentation. I feel like it's better to just help out, instead.

    ---

    Anyway,

    Recursion, in a mathematical sense, is when a function is defined in terms of itself, or basically when the function contains a reference to itself. Therefore, a recursive function can be reduced to a simpler version of itself all the way down to a base case. Let's take a look at the factorial function

    f(n) = 1 for n = 0
    f(n) = n * f(n-1) for n > 0

    As you can see, the function f is included in the definition itself. And there is a base case where the recursion stops (in this case, when n = 0).

    So, f(3) can be rewritten as
    f(3)
    = 3 * f(2)
    = 3 * 2 * f(1)
    = 3 * 2 * 1 * f(0)
    = 3 * 2 * 1 * 1
    = 6

    Now when you look at it from a programmatic perspective, you can see a very similar thing going on. I'll comment your code to show you were they line up.

    Java Code:
    class Factorial
    {
    	int fact(int n) // f(n)
    	{
    		int result;
    		if(n == 1) // f(n) = 1 for n = 1
    			return 1;
    		result = fact(n - 1) * n; // f(n) = n * f(n-1) for n > 1
    		return result;
    	}
    }
    And, when java runs through this code it is essentially saying
    fact(n)
    = fact(n-1) * n
    = fact(n-2) * fact(n-1) * fact(n) ...

    So it's saying
    in order to compute the factorial of 3, I require the factorial of 2
    in order to compute the factorial of 2, I require the factorial of 1
    in order to compute the factorial of 1, I require the factorial of 0
    I have the factorial of 0, now I can compute the factorial of 1
    ...
    ...
    back up to factorial of 3

    Is there any particular part of this you need a more in depth explanation for?
    Last edited by AndrewM16921; 06-24-2013 at 04:36 AM.

  4. #4
    superhaNds is offline Senior Member
    Join Date
    Apr 2013
    Location
    Sweden
    Posts
    264
    Rep Power
    2

    Default Re: Recursion Help!

    Recursion is extremely difficult to grasp and understand, at least for me, even did recursion in discrete maths before doing it in programming and still I have difficulties in some
    more complicated problems.
    The concept is basically that we reduce the problem into a smaller instance of the problem to which we know the answer, in this case n = 1, and the function calls itself as many times as needed until reaching the answer that
    we know.

    btw, the factorial example that we all have seen, doesn't it get a stack overflow if one calls fact(0) ?

  5. #5
    AndrewM16921 is offline Senior Member
    Join Date
    Jan 2009
    Location
    CA, USA
    Posts
    264
    Rep Power
    6

    Default Re: Recursion Help!

    Quote Originally Posted by superhaNds View Post
    btw, the factorial example that we all have seen, doesn't it get a stack overflow if one calls fact(0) ?
    The proper base case for factorial is n=0, then it should throw an IllegalArgumentException or something like that when n < 0. Kinda skipped over that for the sake of explaining recursion itself =p

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,513
    Blog Entries
    7
    Rep Power
    20

    Default Re: Recursion Help!

    Quote Originally Posted by superhaNds View Post
    Recursion is extremely difficult to grasp and understand, at least for me
    Recursion is extremely easy to understand if you're lazy (like me); all you have to do is take care that your recursive function/method doesn't have side effects; the rest is just a direct implementation of the recursive formula you found in a book ...

    kind regrds,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Recursion?
    By Fingerz in forum New To Java
    Replies: 10
    Last Post: 01-08-2011, 02:25 AM
  2. more fun... with recursion
    By sonny in forum New To Java
    Replies: 19
    Last Post: 03-23-2010, 05:09 AM
  3. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  4. Recursion
    By Mika in forum New To Java
    Replies: 5
    Last Post: 01-04-2009, 01:13 AM

Posting Permissions

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