# Google+ Page // Facebook Page // Twitter Page

## 13 Comments

## Leave a comment

Comments temporarily disabled.

# Google+ Page // Facebook Page // Twitter Page

New to Spiked Math?

View the top comics.

View the top comics.

**New Feature:**Browse the archives in quick view! Choose from a black, white or grey background.**Top Math Comics**

(Ranked by SM-CRA)

Other Sites:

I once wrote out the Fibonacci sequence to the 98th number.

I was bored...

He need a pair of rabbits to pass the time.

//yeh on that same topic.../

import java.io.*;

class Fibonacci {

public static void main(String[] args) throws IOException {

PrintWriter wF = new PrintWriter(new BufferedWriter(new FileWriter("Fibonacci.txt")));

long[] Fibonacci = new long [94];

int c=0;

wF.println("The Fibonacci Sequence on its first 100 places:");

Fibonacci[0]=0;Fibonacci[1]=1;

System.out.println("Fibonacci[0] = 0");

wF.println("Fibonacci[0] = 0");

System.out.println("Fibonacci[1] = 1");

wF.println("Fibonacci[1] = 1");

for(c=2;c Fibonacci[c]=Fibonacci[c-1]+Fibonacci[c-2];

System.out.println("Fibonacci["+c+"] = "+Fibonacci[c]+" which is: "+Fibonacci[c-1]+" + "+Fibonacci[c-2]);

wF.println("Fibonacci["+c+"] = "+Fibonacci[c]+" which is: "+Fibonacci[c-1]+" + "+Fibonacci[c-2]);

}

wF.close();

}

}//am i a nerd?/

# reply to the above statement ^ lol no

reply = raw_input("You could do better, ever heard of tail recursion ? reply with yes/no")

If reply.capitalize() == YES : print "yes"

elif reply.capitalize() == NO : print "no"

else : print "can you read?"

recursion for Fibonacci number generation is a very bad idea. using recursion, the time complexity is exponential - o(2^n)

Using iteration, the time complexity is o(n).

Naive recursion fails badly, but naive recursion is not the only recursion. For example:

fib n = fibs !! (n-1) --the nth fibonacci number is the nth entry in the list.

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

is an O(n) recursive implementation of the Fibonacci sequence in Haskell. This particular implementation requires laziness.

Recursion can be used to get a Fibonacci number in O(logn).

By using a recursive function to calculate [1 1;1 0]^n in logarithmic time and multiply it with [1 0] one would obtain [F(n+1);F(n)].

[1 1;1 0]^(n-1)*[1;0]=[F(n);F(n-1)]

I used the matrix representation of matlab.

Use memoization when recursing. Note that without operator overloading, it's gonna look ugly.

It made my recursive Ackermann quite fast. That is, until i had to learn how to play with infinite-size integers :)

Anyways, here's an efficient recursion one:

#include <cstdio>

#include <cstdlib>

#include <map>

using namespace std;

map<unsigned int, unsigned long> memo;

unsigned long fib(unsigned int a) {

if (memo.find(a) != memo.end())

return memo[a];

if (a < 3) {

memo[a] = 1;

return memo[a];

}

memo[a] = fib(a-1) + fib(a-2);

return memo[a];

}

int main(int argc, char **argv) {

memo = map<unsigned int, unsigned long>();

printf("%lu", fib(atoi(argv[1])));

return 0;

}

I don't get the joke :/

Who can explain this joke to me ...

This coding has gotten out of hand...

It's Fibonacci's eighth prison term (his eighth prison sentence)...I don't think that this is a funny joke.

or you guys could just use: ((phi)^(n))/(root5) if n is even, you round down to the largest number if n is odd, round up to next smalled whole number