I am currently doing program 2 for the startup engineering course offered on coursera
I'm programming using and ubuntu instance using Amazon web services and my programming is constantly hanging. There might be something wrong with my node.js program but I can't seem to locate it.
This program is meant to produce the first 100 Fibonacci numbers separated with commas.
#! /usr/bin/env node
//calculation
var fibonacci = function(n){
if(n < 1){return 0;}
else if(n == 1 || n == 2){return 1;}
else if(n > 2){return fibonacci(n - 1) + fibonacci(n-2);}
};
//put in array
var firstkfib = function(k){
var i;
var arr = [];
for(i = 1; i <= k; i++){
arr.push(fibonacci(i));
}
return arr
};
//print
var format = function(arr){
return arr.join(",");
};
var k = 100;
console.log("firstkfib(" + k +")");
console.log(format(firstkfib(k)));
The only output I get is
ubuntu@ip-172-31-30-245:~$ node fib.js
firstkfib(100)
and then the program hangs
I don't know if you are familiar with Time complexity and algorithmic analysis, but, it turns out that your program has an exponential running time. This basically means that, as the input increases, the time it takes to run your program increases exponentially. (If my explanation is not very clear, check this link)
It turns out that this sort of running time is extremely slow. For example, if it takes 1 ms to run your program for k=1, it would take 2^100 ms to run it for k=100. This turns out to be a ridiculously big number.
In any case, as Zhehao points out, the solution is to save the value of fib(n-1) and fib(n-2) (in an array, for example), and reuse it to compute fib(n). Check out this video lecture from MIT (the first 15 mins) on how to do it.
You may want to try printing out the numbers as they are being computed, instead of printing out the entire list at the end. It's possible that the computation is hanging somewhere along the line.
On another note, this is probably the most inefficient way of computing a list of fibonacci numbers. You compute fibonacci(n) and then fibonacci(n+1) without reusing any of the work from the previous computation. You may want to go back and rethink your method. There's a much faster and simpler iterative method.