# Thread: Turning Recursion Method into Iterative method

1. Member
Join Date
Jun 2010
Posts
5
Rep Power
0

## 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);
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?

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

2. 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;]
// 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. Member
Join Date
Jun 2010
Posts
5
Rep Power
0
Honestly no, I don't really understand stacks.

4. 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?
Last edited by Fubarable; 06-15-2010 at 02:07 AM.

5. Member
Join Date
Jun 2010
Posts
5
Rep Power
0
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. Member
Join Date
Jun 2010
Posts
5
Rep Power
0
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.

7. Senior Member
Join Date
Mar 2010
Posts
952
Rep Power
11
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

8. Member
Join Date
Jun 2010
Posts
5
Rep Power
0
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

9. Senior Member
Join Date
Feb 2010
Location
Ljubljana, Slovenia
Posts
470
Rep Power
11
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.

#### Posting Permissions

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