# Turning Recursion Method into Iterative method

• 06-15-2010, 01:20 AM
mattakuevan
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:

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
• 06-15-2010, 01:35 AM
Fubarable
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:

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!
• 06-15-2010, 01:42 AM
mattakuevan
Honestly no, I don't really understand stacks.
• 06-15-2010, 02:00 AM
Fubarable
Quote:

Originally Posted by mattakuevan
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?
• 06-15-2010, 02:35 AM
mattakuevan
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.
• 06-15-2010, 02:44 AM
Fubarable
You may wish to show here the numbers that you get, in order.
• 06-15-2010, 02:55 AM
mattakuevan
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.
• 06-15-2010, 03:09 AM
gcalvin
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-
• 06-15-2010, 03:44 AM
mattakuevan
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
• 06-15-2010, 06:46 AM
m00nchile
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:
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.