Recursion

[Stacey Johnson]

Hi all!
I'm new to this sight and I already love it! I am taking a begginer course in java and I'm asked to write a non-recursive method that computes fibonacci numbers. I sort of understand what fibonacci numbers are but I really don't understand the whole recursion thing. Can anybody explain to me in layman's terms what recussive and non-recurssive methods are?
I would really appreciate it.
Thank you
Stacey

[frank vallee]

Hi Stacey
Recursion is a technique where a method calls itself again an againg until a certain breaking condition occurs. I don't remember the fibronacci formula but here is a small program computing the factorial first with and then without recursion:

public class FactorialTest {
public long recursiveFactorial(long f){
if(f==0)
return 1;
else
return f*recursiveFactorial(f-1);
}
public long loopingFactorial(long f){
if(f==0)
return 1;
long result = f;
for(int i=(int)f-1;i>0;--i){
result*=i;
}
return result;
}
public static void main(String[] args){
FactorialTest ft = new FactorialTest();
long op = Long.parseLong(args[0]);
System.out.println("Result of recursiveFactorial for "+op+" is : "+ft.recursiveFactorial(op));
System.out.println("Result of loopingFactorial for "+op+" is : "+ft.loopingFactorial(op));
}
}

If you call the program with 5 as argument, the recursive method will call itself 5 time with one substracted at each recursion. The total sequence is recursiveFactorial(5) * recursiveFactorial(4) * ... * recursiveFactorial(0) (ie: 5*4*3*2*1*1=120 )
Good luck.
Frank

[Mr. C Lamont Gilbert]

another point of interest is stack space. One often avoids recursive methods because they can use lots of stack space.
each time a method is invoked it takes up some stack space until that method exits. The recursive method will continue to take more stack space at each new call of the method until the final method is reached and exited.
if you put a BIG number in the recursive method it can throw an StackOverflowException or the like. The non-recursive method will not.