Results 1 to 10 of 10
  1. #1
    mattakuevan is offline Member
    Join Date
    Jun 2010
    Posts
    5
    Rep Power
    0

    Default Turning Recursion Method into Iterative method

    Hello, I'm relatively new to java and I am sort of stuck on how exactly I would turn a previously defined recursive method into another method only using iteration.

    Here is my current code:

    Java Code:
    import java.util.Scanner;
    
    public class RecursiveLab
    {	
    	public static void main(String [] args)
    	{
    		Scanner scan = new Scanner(System.in);
    		System.out.print("Please enter an integer: ");
    		int userChoice = scan.nextInt();
    		int result = mystery(userChoice);
    		System.out.println("The result was: " + result);
    	}
    	
    	public static int mystery(int num)
    	{
    		if(num <= 2)
    			return 1;
    		else
    			return mystery(num - 1) + mystery(num - 2);
    	}
    	
    	public static int mystery2(int num)
    	{
    		int sum = 0;
    		
    		return sum;
    	}
    
    }

    Mystery is the recursive and mystery2 is going to be the iterative. Don't worry about the main not calling it, that will come later. I'm just looking at a new version for my mystery method.

    Anyone have any good ideas to accomplish this?

    Moderator Edit: Code tags added
    Last edited by Fubarable; 06-15-2010 at 01:33 AM. Reason: Moderator Edit: Code tags added

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

    Default

    Hello, and welcome to the forum. I hope you don't mind that I edited your code and added code tags which should help make your posted code retain its formatting and be more readable.

    To do this yourself, highlight your pasted code (please be sure that it is already formatted when you paste it into the forum; the code tags don't magically format unformatted code) and then press the code button, and your code will have tags.

    Another way to do this is to manually place the tags into your code by placing the tag [cod&#101;] above your pasted code and the tag [/cod&#101;] below your pasted code like so:

    Java Code:
    [cod&#101;]
      // your code goes here
      // notice how the top and bottom tags are different
    [/cod&#101;]
    Regarding your question, are you familiar with the use of stacks? As this is one way to change a recursive problem into an iterative problem.

    Best of luck, and again, welcome!

  3. #3
    mattakuevan is offline Member
    Join Date
    Jun 2010
    Posts
    5
    Rep Power
    0

    Default

    Honestly no, I don't really understand stacks.

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

    Default

    Quote Originally Posted by mattakuevan View Post
    Honestly no, I don't really understand stacks.
    They are useful in a general sense when trying to change from recursion to iteration, but your code can be changed much more easily, and if you run it a few times, you'll see the pattern and thereby figure out a simple non-recursive method that will work. By the way, do you know what this series is called?
    Last edited by Fubarable; 06-15-2010 at 02:07 AM.

  5. #5
    mattakuevan is offline Member
    Join Date
    Jun 2010
    Posts
    5
    Rep Power
    0

    Default

    Not really, I was given this as an assignment in class and my teacher didn't really talk about it at all. I've never seen this before.

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

  7. #7
    mattakuevan is offline Member
    Join Date
    Jun 2010
    Posts
    5
    Rep Power
    0

    Default

    Ok, so numbers inputted were: 7, 14, 35, 40, 42, 45

    The resulting numbers were: 13, 377, 9227465, 102334155, 267914296, 1134903170

    It pretty much just counts the number of times the num value less than or equal to 2, or at least I think that is what it is doing.

    Numbers (1-7) give 1, 1, 2, 3, 5, 8, 13 if you guys want a smaller idea of what exactly is happening in this program.

  8. #8
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

    What you have is a Fibonacci method. The Fibonacci series is defined as:

    F(1) = 1;
    F(2) = 1;
    F(n) = F(n-1) + F(n-2) where n > 2.

    At first glance, it seems that recursion is a good way to generate Fibonacci numbers, as the series is self-referential. But if you do it in a recursive method without memoization, your method ends up doing the same work multiple times.

    To calculate Fibonacci numbers iteratively, just keep adding the last number to the current number, and that gives you the next number. Then of course next becomes current and current becomes last, and you do it again. Meanwhile, you keep a counter so you know where you are in the series.

    Give it a try and show us what you come up with.

    -Gary-
    Last edited by gcalvin; 06-15-2010 at 04:04 AM. Reason: Fixed stupid typing mistake

  9. #9
    mattakuevan is offline Member
    Join Date
    Jun 2010
    Posts
    5
    Rep Power
    0

    Default

    Ok, got it up and running and for the numbers posted I got the same values as before (that's good).

    I did notice that the iterative version was SIGNIFICANTLY faster to calculate than the recursive method. I'm assuming that was the result my teacher had intended I would discover.

    Thanks guys :D

  10. #10
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    That isn't necesarrily true, this implementation of recursion was slower for a particular reason, the way it is defined means that one number will be calculated multiple times. Try this on for size:
    Java Code:
    public class FasterRecursion {
      public static void main(String[] args) {
        int n;
        if(args.length == 0)
          n = 10;
        else
          n = Integer.parseInt(args[0]);
        System.out.println(fib(n));
      }
    
      private static int fib(int n) {
        Integer[] memo = new Integer[n+1];
        return fib(n, memo);
      }
    
      private static int fib(int n, Integer[] memo) {
        if(n <= 1) memo[n] = n;
        if(memo[n] == null) {
          memo[n] = fib(n-1, memo) + fib(n-2, memo);
        }
       return memo[n];
      }
    }
    If you need further explanation post it here. And run this method, and the one your teacher posted for a large n value, see the difference.
    And about the stack usage to turn recursion into iteration that has been suggested by others, that is the standard way of turning recursion into iteration. If you have tail recursion, you can trasform it to iteration just with a loop, otherwise, using the stack is necessary.
    Last edited by m00nchile; 06-15-2010 at 06:48 AM.
    Ever seen a dog chase its tail? Now that's an infinite loop.

Similar Threads

  1. Replies: 2
    Last Post: 03-26-2010, 05:12 PM
  2. Replies: 1
    Last Post: 03-17-2010, 05:25 AM
  3. Replies: 3
    Last Post: 02-09-2010, 05:22 AM
  4. My first recursion method: the number e
    By Lil_Aziz1 in forum Reviews / Advertising
    Replies: 1
    Last Post: 01-23-2010, 10:28 PM
  5. implement binary search method using recursion?
    By chopo1980 in forum New To Java
    Replies: 1
    Last Post: 12-12-2009, 03:58 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
  •