Results 1 to 11 of 11

Thread: Recursion?

  1. #1
    Fingerz is offline Member
    Join Date
    Jan 2011
    Posts
    8
    Rep Power
    0

    Default Recursion?

    Hi all,

    Only been programming a few days now. Got to this section about recursion. Completely confused on how each pass throu the recursive method is being stored until its base case is reached and then calculates from the base case back to 5.

    With an argument of 5 being passed f.fact(5)

    class factorial{
    int fact(int n){
    int result;

    if(n==1) return 1;
    result = fact(n-1)*n;
    return result;
    }
    }

    The book only has 2 paragraphs about this subject. Anyone have the patience to helps me understand the inner workings of this would be greatly appreciate. Or some good sites I can use for some better info. TYVM.

  2. #2
    travishein's Avatar
    travishein is offline Senior Member
    Join Date
    Sep 2009
    Location
    Canada
    Posts
    684
    Rep Power
    6

    Default

    internally in the Java VM is what's called a "stack" this is kind of like a stack of plates at a buffet, or the pile of things to do on my desk. where you have a piece of paper with a state and some scribbles on it, (e.g. variable) and then if you were to put another piece of paper over top of that, it has its own space to put variables, possible a varibale name with different values..

    so when a function is executed, the current location of the program is stored into the stack, as a "come back to this spot when the function is finished executing."
    Within a function, any variables are allocated into the stack (more pices of paper piled up on top of the previous ones), as scratch pads during the scope of the function execution, when the function returns, these are cleaned up.

    so recursive functions are a function that calls itself. each invocation of the function has its own 'piece of paper' to store its local variables and function parameter values that it was passed.

    in this case, the terminal case is inside the function when it evaluates the parameter passed into it was 1, it simply returns. the program control then returns to the previous function, which its local variables are evaluated, and it returns until all the functions states stored on the stack are back to the main() method and the program exits.

  3. #3
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    Check out htdp.org if you want to get a better understanding of how recursion works, the book uses lots of it, and the programming language has a nice visual display of how a program is evaluated so you can see what happens at each step.

  4. #4
    Fingerz is offline Member
    Join Date
    Jan 2011
    Posts
    8
    Rep Power
    0

    Default

    Ok,
    I understood that stacks relied on push and pop, throu arrays. Are those the stacks your refering too? Does Java automatically view recursion and create the stack itself, until the base case is reached? Or amI missing the point?

  5. #5
    ClickerMonkey is offline Member
    Join Date
    Jan 2011
    Posts
    12
    Rep Power
    0

    Default

    Every time you make a method call you add (push) that 'method' on the stack. Once the method completes it is then removed (popped) off the stack. With recursion you calling method X which is pushed on the stack, in method X it calls method X until some condition - continually pushing more X on the stack... once the condition is met each method is popped off one at a time and finish execution.

    I hope this perspective has helped!

  6. #6
    Fingerz is offline Member
    Join Date
    Jan 2011
    Posts
    8
    Rep Power
    0

    Default

    Ok another question.
    Is recursion a built in java class that reconizes that your method is recursive.
    So it knows not to process a method until the base case is reached. Once that base case is reached its works its way back up the stack implemented each method on the stack until its base case is reached again. So on and so on until the stack is empty. Only been doing this a few like said earlier so my terminology might be off. Feel free to correct me, actually I would appreciate it :)

  7. #7
    Singing Boyo is offline Senior Member
    Join Date
    Mar 2009
    Posts
    552
    Rep Power
    6

    Default

    Recursion is when a method calls itself. Java has no need to notice that your method is recursive. It does exactly the same thing with recursive calls as it does with normal method calls. All a program in any language really is is a stack of method calls, and when you end up with the last of the method calls removed from the stack, the program exits. Programs with multiple threads have multiple call stacks - one for each thread, and they only exit, in the case of java, when the stack for all of the threads are empty. (If you don't know what threads are, then don't worry about it.)
    If the above doesn't make sense to you, ignore it, but remember it - might be useful!
    And if you just randomly taught yourself to program, well... you're just like me!

  8. #8
    Fingerz is offline Member
    Join Date
    Jan 2011
    Posts
    8
    Rep Power
    0

    Default

    Ok then what Im confused about is how each value is being return from one method to the next.

    with result = fact(n-1) * n
    with the argument of f.fact(5) being passed
    I see result = (5-1) * 5 given me 20, and not 120 like it sould be.
    So what Im not understanding is how the factorial values are being passed back up to the stack. If you could put in terms of how each is being evauluated thats would help a great deal.

  9. #9
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    alright, when the function is called it first determines if it's at the base case.

    For factorial the base case is 1.
    if the base case is not met, it moves on, the second case in factorial would be:
    Java Code:
    n * factorial(n - 1);
    not n * n -1 like you are thinking.

    so when it gets the the second case it calls its self with a smaller number.
    it continues calling its self until the case of factorial 1 is sent to the stack, when it is, it evaluates to 1 and all the stuff previously on the stack.

    so you get n * n - 1 * n - 2 ... * 1.

    Java Code:
    int factorial(int n)
    {
     if(n == 1)
    {
       return 1;
     }
     else
    {
       return  n * factorial(n - 1);
    }
    }
    for factorial of 5 it works like this
    Java Code:
    5 == 1? no.
    so
    5 * factorial(4);
    does 4 == 1? no.
    4 * factorial(3);
    3 * factorial(2);
    2 * factorial(1);
    1.
    once one is met it "cleans up" so to say(probably the wrong term, but it gets my point accross) it goes through the stack and performs the operations.

  10. #10
    Fingerz is offline Member
    Join Date
    Jan 2011
    Posts
    8
    Rep Power
    0

    Default

    TYVM thats what I was looking for to easy lol. TY you all for your time:)

  11. #11
    sunde887's Avatar
    sunde887 is offline Moderator
    Join Date
    Jan 2011
    Location
    Richmond, Virginia
    Posts
    3,069
    Blog Entries
    3
    Rep Power
    8

    Default

    Also, if you want a website with some pretty decent recursion problems to play around with and get more familiar, here is a link: CodingBat Java Recursion-1

Similar Threads

  1. more fun... with recursion
    By sonny in forum New To Java
    Replies: 19
    Last Post: 03-23-2010, 06:09 AM
  2. Recursion
    By mp0667 in forum New To Java
    Replies: 1
    Last Post: 01-20-2010, 08:49 AM
  3. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 PM
  4. Recursion
    By kathyla18 in forum New To Java
    Replies: 2
    Last Post: 04-09-2009, 03:26 AM
  5. Recursion
    By Mika in forum New To Java
    Replies: 5
    Last Post: 01-04-2009, 02: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
  •