# Iteration to Recursion

• 06-22-2011, 01:28 AM
fam2315
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

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:

Code:

```void Recursion(int n) {  if ( f(i) == TRUE) {  /*some code that does not change i*/  Recursion(g(i));  } }```
• 06-22-2011, 01:39 AM
Junky
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.
• 06-22-2011, 01:49 AM
fam2315
do you think I am on the right track with this one?
• 06-22-2011, 02:02 AM
sunde887
Quote:

Originally Posted by Junky
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.

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
• 06-22-2011, 02:31 AM
fam2315
with my particular problem, I'm not seeing how it can be implemented recursively, since we need a base case?
• 06-22-2011, 02:35 AM
Junky
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?).
• 06-22-2011, 02:42 AM
fam2315
so this would seem logical?

Code:

```void Recursion(int n) int i = n; {  if ( f(i) == TRUE) {  /*some code that does not change i*/  Recursion(g(i));  } }```
• 06-22-2011, 02:58 AM
Junky
I guess it depends upon what f and g methods do but it looks like it should be OK.