Wednesday, December 23, 2009

Generate Fibonacci series using recursion with ColdFusion

Recursion is a method which has been popular from the earlier age of computing. In simple terms, recursion is the process in which a function/method calls itself again and again till a condition is satisfied. It is mainly used to generate or find the sum of series of numbers like Fibonacci series.
I seldom had chance to implement the recursion in programming. Lately I had to create a dynamic menu structure using Ext JS and I found recursion was the answer. I was able to neatly create the menu dynamically to 'n' levels.
As the creation of menu includes Ext JS and other dependencies, I will try to explain the concept with generating Fibonacci series numbers in ColdFusion.

As noted before, recursion is the process of a function calling itself again and again. It is infinite, so we will restrict our demo to values till 50 .

Let us first look what a fibonacci series is. The series propagates in a manner such that a number in the series is the sum of two preceeding numbers and the series starts with 1 and 1.

Fibonacci series:
1,1,2,3,5,8,13,21,...
We need to create a function which calls itself again and again to generate fibonacci numbers and also to find the sum of those numbers. Let us call it 'doRecursion'.

The logic is, the function will receive two numbers as arguments. It should add up the two numbers to get the third number. But the sum of second number and third number is the fourth number and so on.

For example,
Step 1: we get two numbers 1 and 1. so the third number is
1+1=2
Step 2: fourth number is 2nd + 3rd number, i.e, 1+2 = 3.
Step 3: fifth number is 3rd + 4th number, i.e, 2+3 = 5.

That is, we get two numbers, whose sum is third number. But the second one among the two numbers and their sum adds to give fourth number, and the series goes on.

So, our function will take two numbers as arguments and instead of simply adding the two, add the first number to the recursive call whose input will be the second number and the sum of first and second number. The return value of the function is the first argument itself.

Code:

doRecursion(1,1); //Initiating the call

function doRecursion(value1,value2)
{
if(value2 LTE 50) //A simple condition to restrict the loop
{
/* Adding the first number with the return value of recursive call to the doRecursion function with the arguments as the second number and the sum of first and second number */
writeoutput(value1 + doRecursion(value2,value1+value2)&" ");
}
return value1;
}

First we call the function doRecursion with the arguments 1,1. Now the function will try to add the value1 with the return value of the call to function doRecursion by passing the parameters value2 and sum of value1 and value2. This function will return the first argument so that it will get added to the value1 in the main function.

Now run the code and see the result.
55 34 21 13 8 5 3 2

and... what happened? the series is in reverse...
Ok, let me explain this.
When we call the function, it will try to add the value1 to the result of another function call and so the control is never returned to the calling function until... the value2 greater than 50. In this case, the call to the function is not performed and it will return the first argument as return value to the called function which in turn completes the calculation. So, the value 55 gets displayed first because at that instance the value1 = 34 and value2=55 and value2 is greater than 50. So, the function will return the first value (34) to the calling function which was waiting to add it with it's first argument 21 and that function returns it's first argument ie, 21 to its calling function and so on.

   So, the values gets displayed in reverse order.

Now make a small change in the function.

if(value2 LTE 50) //A simple condition to restrict the loop
{
writeoutput(value1&" ");
doRecursion(value2,value1+value2);
}

Now, the result will be
1 1 2 3 5 8 13 21
Hope the logic is clear.