Results 1 to 8 of 8
  1. #1
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default Iteration to Recursion

    Is there a general rule that can be followed to go from an iterative method to one that is recursive?

    I need help transforming the following method to a recursive one

    Java Code:
    void Iteration(int n)
    {
    *** int i;
    *** i = n;
    *** while ( f(i) == TRUE ) {
          /*some code that does not change i*/
    ** **** i = g(i);
    *** }
    }
    I was thinking something like:

    Java Code:
    void Recursion(int n)
    {
     if ( f(i) == TRUE) {
     /*some code that does not change i*/
     Recursion(g(i));
     }
    }

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,800
    Rep Power
    7

    Default

    No there is not a single general rule. Different recursive methods do different things so there is no way you can apply the same rule to all of them. Just as an example Factorial makes a single recursive call while Fibonacci makes 2 recursive calls. How is a single rule supposed to apply to those situations? About the only common thing that can be applied to recursion is: determine what your base case is. That is when do you stop making recursive calls.

  3. #3
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    do you think I am on the right track with this one?

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

    Default

    Quote Originally Posted by Junky View Post
    Just as an example Factorial makes a single recursive call while Fibonacci makes 2 recursive calls.
    Nitpick: not necessarily, it is more than possible to find the nth fibonnaci number with one recursive call via an iterative recursive process rather than tree recursive.

    Java Code:
    public int fibb(int count, int a, int b){
      if(count == 0)
        return a;
      else{
        return fibb((count - 1), (a + b), a);
      }
    } 
    public int fibb(int n){
      return fibb(n, 1, 0);
    }
    The example might be a bit off, I'm too lazy to compile it right now, but it's along this general idea.

    @op: junky is right, there is no rule to converting an iterative approach to a recursive one, especially since there can also be multiple recursive approaches, in my snippet above it's an alternate way to compute fibb numbers to the one junky mentioned.

    I wrote a small blog on recursion if you are interested, here is the link:
    http://www.java-forums.org/blogs/sun...recursion.html

  5. #5
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    with my particular problem, I'm not seeing how it can be implemented recursively, since we need a base case?

  6. #6
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,800
    Rep Power
    7

    Default

    You do have a base case. As soon as f(i) returns false the recursive calls stop and it goes back up the call stack (or is that down?).

  7. #7
    fam2315 is offline Member
    Join Date
    Feb 2011
    Posts
    78
    Rep Power
    0

    Default

    so this would seem logical?

    Java Code:
    void Recursion(int n)
    
    int i = n;
    {
     if ( f(i) == TRUE) {
     /*some code that does not change i*/
     Recursion(g(i));
     }
    }

  8. #8
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,800
    Rep Power
    7

    Default

    I guess it depends upon what f and g methods do but it looks like it should be OK.

Similar Threads

  1. Real life example of iteration
    By fam2315 in forum New To Java
    Replies: 1
    Last Post: 06-19-2011, 09:33 PM
  2. Two Dimensional Array Iteration Help
    By Stamoulohta in forum New To Java
    Replies: 5
    Last Post: 03-13-2011, 02:39 PM
  3. Double Iteration Over a Hashmap
    By Gusy in forum New To Java
    Replies: 1
    Last Post: 12-01-2010, 02:01 AM
  4. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 07:26 PM
  5. Enum Iteration
    By A.Russell in forum New To Java
    Replies: 1
    Last Post: 08-15-2007, 01:17 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
  •