In many beginning computer science courses, an introduction to the concept of recursion often includes a program to calculate and print Fibonacci numbers (or computing the factorial of a number). Recursion is a very important idea in computer programming as it is often used by programmers to implement complex algorithms using a few lines of code. Since the Fibonacci sequence is easy to describe and understand, this is often the first example used to illustrate the concept. The following list includes examples of code in various programming languages that will calculate the Fibonacci sequence. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ... In mathematics, the Fibonacci numbers form a sequence defined recursively by: That is, after two starting values, each number is the sum of the two preceding numbers. ... The beginning of the sequence of factorials (sequence A000142 in OEIS) In mathematics, the factorial of a natural number n is the product of all positive integers less than or equal to n. ...

Background

Main article: Fibonacci number

The Fibonacci sequence is a recursive sequence defined as: In mathematics, the Fibonacci numbers form a sequence defined recursively by: That is, after two starting values, each number is the sum of the two preceding numbers. ...

In simple terms, each number is the sum of the previous two numbers, with the first and second term 0 and 1 respectively. The first Fibonacci numbers (sequence A000045 in OEIS) for n = 0, 1, … are

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …

Motivation

The Fibonacci sequence, although simple, can be used to introduce many techniques and issues with computer programming, it has even been called "computer science’s favorite sequence." ^[1] A common teaching technique is to have students write the program prior to knowledge of recursion, using for loops:

 var prev_fib[2] : int : {0, 1} var new_fib : int print prev_fib[0] print prev_fib[1] for x : 1 .. n newfib := prev_fib[0] + prev_fib[1] print new_fib prev_fib[0] = prev_fib[1] prev_fib[1] = new_fib end for 

The Fibonacci sequence is also a popular introductory program for recursion (along with factorials) in computer science classes. Its code follows straight from the definition: In mathematics, the factorial of a natural number n is the product of the positive integers less than or equal to n. ...

 function fib (n : int) : int if (fib = 0) return 0 else if (fib = 1) return 1 else return fib (n-1) + fib(n-2) end fib 

Although the above program may appear optimal, there are many problems with it. First, the numbers grow very fast, about 2^0.694n[1], where n is the input. a 32-bit signed int can hold 2³¹-1, which limits the program to about the 44^th term. Use of larger data types is necessary. Secondly, this algorithm runs in O(2ⁿ). Even on the worlds fastest supercomputer, IBM's Blue Gene/L, which clocks at 280.6 TFLOPS^[2], to calculate f(100) would require at least 32 days. The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... now. ... Blue Gene/L Blue Gene is a computer architecture project designed to produce several next-generation supercomputers, designed to reach operating speeds in the petaflops range, and currently reaching speeds over 280 teraflops (sustained). ...

The problem lies in the recursive nature of the sequence. To calculate f(4) we must first calculate f(3) and f(2). When we are calculating f(3), we calculate f(2) + 1, which duplicates the calculation of f(2). For large values of n this problem renders the algorithm useless. Instead of throwing away all of our previous calculations, we can store them in a map and only calculate as necessary. It has been suggested that Map (C++ container) be merged into this article or section. ...

 var m := map(0 → 1, 1 → 1) function fib(n) if n not in keys(m) m[n] := fib(n − 1) + fib(n − 2) return m[n] 

This algorithm stores all solutions and reuses them to calculate new values (i.e. if f(4) and f(3) are stored, f(5) can be calculated by simply adding the two numbers together, without calculating them.) This reduces the time complexity to O(n²), (not O(n) because addition of the larger numbers will be slower) with the tradeoff that solutions have to be stored in memory. This is an introduction into dynamic programming and memoization as well as optimization. The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ... Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ... It has been suggested that Loop optimization be merged into this article or section. ...

Common Lisp

The following Common Lisp code segment demonstrates how to calculate the Fibonacci sequence using Lucas' formula. Common Lisp, commonly abbreviated CL (not to be confused with Combinatory logic which is also abbreviated CL), is a dialect of Lisp, standardised by ANSI X3. ...

 (defun fib (n) (cond ((= n 0) 0) ((or (= n 1) (= n 2)) 1) ((= 0 (mod n 2)) (- (expt (fib (+ (truncate n 2) 1)) 2) (expt (fib (- (truncate n 2) 1)) 2))) (t (+ (expt (fib (truncate n 2)) 2) (expt (fib (+ (truncate n 2) 1)) 2))))) (fib (parse-integer (second *posix-argv*))) ; 

Haskell

The following Haskell code segment demonstrates how to calculate the Fibonacci sequence using an infinite list. Haskell is a standardized pure functional programming language with non-strict semantics, named after the logician Haskell Curry. ...

 fibo = 0 : 1 : zipWith (+) fibo (tail fibo) 

While the previous is the "canonical" Haskell way to implement the algorithm, one can also use more common styles:

Recursive from Definition

 fib :: Integer -> Integer fib 0 = 0 fib 1 = 1 fib x = fib (x-1) + fib (x-2) 

The only point of this exercise is that it looks exactly like the mathematical definition

Tail-recursive

 fib :: Integer -> Integer fib x = fibRec x 0 1 where fibRec :: Integer -> Integer -> Integer -> Integer fibRec 0 a _ = a fibRec x a b = fibRec (x-1) b (a+b) 

Io

The following Io code segment demonstrate how to calculate the Fibonacci sequence using a logarithmic time recursion.

 fib := method(n, if(n < 3, (n + n % 2) / 2, (n % 2 * 2 - 1) * fib((n + n % 2) / 2 - 1) ** 2 + fib((n - n % 2) / 2 + 1) ** 2 ) ) 

Perl

The following Perl code segments demonstrate how to calculate the Fibonacci sequence using iteration, binary recursion, and memoization. Programming Republic of Perl logo Perl, also Practical Extraction and Report Language (a backronym, see below), is a programming language released by Larry Wall on December 18, 1987 that borrows features from C, sed, awk, shell scripting (sh), and (to a lesser extent) from many other programming languages. ... The word iteration is sometimes used in everyday English with a meaning virtually identical to repetition. ... Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ...

Iterative

 sub fibo { my ($n, $a, $b) = (shift, 0, 1); ($a, $b) = ($b, $a + $b) while $n-- > 0; $a; } 

Binary recursion

 sub fibo { $_[0] < 2 ? $_[0] : fibo($_[0] - 1) + fibo($_[0] - 2) } 

Runs in Θ(F(n)) time, which is Ω(1.6ⁿ). It has been suggested that this article or section be merged into Asymptotic notation. ...

Perl's builtin memoization module

 use Memoize; sub fibo { $_[0] < 2 ? $_[0] : fibo($_[0] - 1) + fibo($_[0] - 2) } memoize 'fibo'; 

Explicit memoization

 { my @memo = (0, 1); sub fibo { $memo[$_[0]] ||= fibo($_[0] - 1) + $memo[$_[0] - 2] } } 

Command line iterative

 perl -Mbigint -le '$a = 1; print $a += $b while print $b += $a' 

Prolog

The following Prolog code generates the first 20 numbers of the sequence given 0 and 1 as the starting numbers, using recursion. Prolog is a logic programming language. ...

 fib(_, _, 0):- !. fib(T1, T2, N):- T is T1 + T2, N1 is N - 1, write(T), nl, fib(T2, T, N1). 

 run:- fib(0, 1, 20). % work out the first 20 

PostScript

The following PostScript code segments demonstrate how to calculate the Fibonacci sequence using iteration and recursion. This article or section does not cite its references or sources. ... A Sierpinski triangle —a confined recursion of triangles to form a geometric lattice. ...

Iterative

 20 % how many Fibonacci numbers to print 1 dup 3 -1 roll { dup 3 -1 roll dup 4 1 roll add 3 -1 roll = } repeat 

Stack recursion

This example uses recursion on the stack.

 % the procedure /fib { dup dup 1 eq exch 0 eq or not { dup 1 sub fib exch 2 sub fib add } if } def % prints the first twenty fib numbers /ntimes 20 def /i 0 def ntimes { i fib = /i i 1 add def } repeat 

Python

The following Python code segments demonstrate how to calculate the Fibonacci sequence using recursion, a generator, and a matrix equation. Python is an interpreted programming language created by Guido van Rossum in 1990. ... Look up matrix in Wiktionary, the free dictionary. ...

Recursion

Exponential time algorithm

 def fib(n): if n < 2: return n else : return fib(n - 1) + fib(n - 2) 

Logarithmic time algorithm

 def fib(n): if n < 3: return 0 + (0 < n) elif n % 2: return fib(n / 2 + 1) ** 2 + fib((n - 1) / 2) ** 2 else : return fib(n / 2 + 1) ** 2 - fib((n - 1) / 2) ** 2 

Generator

 def fib(): a, b = 0, 1 while True: yield a a, b = b, a + b 

Matrix equation

 def mul(A, B): a, b, c = A d, e, f = B return a*d + b*e, a*e + b*f, b*e + c*f def pow(A, n): if n == 0: return A elif n % 2 : return mul(A, pow(mul(A, A), n / 2)) else : return pow(mul(A, A), n / 2) def fib(n): if n < 2: return n else : return pow((1, 1, 0), n - 1)[0] 

This calculates the nth Fibonacci number in O(log N) time, from the matrix equation It has been suggested that this article or section be merged into Asymptotic notation. ... Logarithms to various bases: is to base e, is to base 10, and is to base 1. ... In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, a table consisting of abstract quantities that can be added and multiplied. ...

and by using exponentiating by squaring. Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number. ...

Scheme

The following Scheme code segments demonstrate how to calculate the Fibonacci sequence using binary recursion and tail-end recursion. Scheme is a multi-paradigm programming language and a dialect of Lisp which supports functional and procedural programming. ... In computer science, tail recursion is a special case of recursion that can be easily transformed into an iteration. ...

Binary recursion, snippet

 (define fibo (lambda (x) (if (< x 2) x (+ (fibo (- x 1)) (fibo (- x 2)))))) 

Runs in Θ(F(n)) time, which is Ω(1.6ⁿ). It has been suggested that this article or section be merged into Asymptotic notation. ...

Tail-end recursive, snippet

 (define (fibo x) (define (fibo-iter x a b) (if (= x 0) a (fibo-iter (- x 1) b (+ a b)))) (fibo-iter x 0 1)) 

Runs in Θ(n) time. It has been suggested that this article or section be merged into Asymptotic notation. ...

Tail-end recursive, snippet

 (define (fib n) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a b (+ (* p p) (* 2 p q)) (+ (* p p) (* q q)) (/ count 2))) (else (fib-iter (+ (* (+ a b) p) (* a q)) (+ (* a p) (* b q)) p q (- count 1))))) (fib-iter 1 0 1 0 n)) 

Suggested by Structure and Interpretation of Computer Programs. Runs in Θ(log(n)) time. Front cover Structure and Interpretation of Computer Programs (SICP) is a textbook published in 1985 about general computer programming concepts from MIT press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman. ... It has been suggested that this article or section be merged into Asymptotic notation. ...

Display all, snippet

 (define (fibo-run a b) (display a) (newline) (fibo-run b (+ a b))) 

 (define fibo-run-all (fibo-run 0 1))) 

C/C++/Java

The following C/C++ code segments demonstrate how to calculate the Fibonacci sequence using recursion and iteration. They will run with minor modification in Java. Wikibooks has a book on the topic of C Programming The C programming language (often, just C) is a general-purpose, procedural, imperative computer programming language developed in the early 1970s by Dennis Ritchie for use on the Unix operating system. ... C++ (generally pronounced /si plÊŒs plÊŒs/) is a general-purpose, high-level programming language with low-level facilities. ... Java is an object-oriented programming language developed by James Gosling and colleagues at Sun Microsystems in the early 1990s. ...

Recursive snippet

 unsigned fib(unsigned n) { if (n < 2) return n; else return fib(n-1) + fib(n-2); } 

Runs in Θ(F(n)) time, which is Ω(1.6ⁿ). It has been suggested that this article or section be merged into Asymptotic notation. ...

Iterative snippet

 unsigned fib(unsigned n) { int first = 0, second = 1; // this while loop will exit when the int reaches 0 // it is equivalent to while(n != 0) { n-- .... } while (n--) { unsigned tmp = first+second; first = second; second = tmp; } return first; } 

Shorter iteration

This version depends on the identities:

Using these tightens up the iteration. Instead of iterating n times to calculate F(n), this function iterates only log(n) times:

 unsigned fib (unsigned n) { unsigned a = 1, b = 0; unsigned i = 0x8000; while (i) { unsigned aa; aa = n&i ? (2*b+a)*a : a*a+b*b; b = n&i ? a*a+b*b : b*(2*a-b); a = aa; i >>= 1; } return b; } 

It is essentially equivalent to the versions that employ matrix arithmetic, but with redundant calculations eliminated. Note that this method only makes sense for high-precision calculations where the benefit of an O(log n) algorithm outweighs the extra complexity. Since F(48) exceeds 2³² - 1, no ordinary C program with 32-bit integers can calculate F(n) for n ≥ 48, and the sophisticated algorithm in this version is just over-engineering.

Pascal

The following Pascal code segments demostrate function written in Pascal programming language:

Function

 {Recursive snippet} function fib(N:integer) : integer; begin if N < 2 then fib := N else fib := fib (N - 1) + fib (N - 2); end; 

Ada

The following Ada code segments demonstrate how to calculate the Fibonacci sequence using recursion and iteration. Ada is a structured, statically typed imperative computer programming language designed by a team led by Jean Ichbiah of CII Honeywell Bull during 1977–1983. ...

Recursive snippet

 function Fib (N : Integer) return Integer is begin if N < 2 then return N; else return Fib (N - 1) + Fib (N - 2); end if; end Fib; 

Iterative snippet

 function Fib (N : Integer) return Integer is First : Integer := 0; Second : Integer := 1; Tmp : Integer; begin for I in 1 .. N loop Tmp := First + Second; First := Second; Second := Tmp; end loop; return First; end Fib; 

MATLAB

The following MATLAB code segments demonstrate how to calculate the Fibonacci sequence using recursion and iteration. MATLAB is a numerical computing environment and programming language. ...

Recursive snippet

 function F = fibonacci_recursive(n) if n < 2 F = n; else F = fibonacci_recursive(n-1) + fibonacci_recursive(n-2); end 

Iterative snippet

 function F = fibonacci_iterative(n) first = 0; second = 1; third = 0; for q = 1:n, third = first + second; first = second; second = third; end F = first; 

CFML

The following CFML code segment demonstrates how to calculate the Fibonacci sequence. CFML may mean: ColdFusion Markup Language, a scripting language for ColdFusion, CFML, a radio station in Vancouver, British Columbia. ...

Recursive Snippet

 <cffunction name="fib" returntype="numeric"> <cfargument name="num" type="numeric" required="true"/> <cfif Arguments.num lt 2> <cfreturn Arguments.num/> <cfelse> <cfreturn fib(Arguments.num - 1) + fib(Arguments.num - 2)/> </cfif> </cffunction> 

PHP scripting language

The following PHP scripting language code segment demonstrates how to calculate the Fibonacci sequence. PHP (PHP: Hypertext Preprocessor) is a reflective programming language originally designed for producing dynamic Web pages. ...

Contained snippet

 function generate_fibonacci_sequence( $length, $method = 0 ) { if( $method == 0 ): // -- standard addition - limited by the capacity (int) for( $l = array(1,1), $i = 2, $x = 0; $i < $length; $i++ ) $l[] = $l[$x++] + $l[$x]; elseif( $method == 1 ): // -- arbitrary precision addition - more process intensive for( $l = array(1,1), $i = 2, $x = 0; $i < $length; $i++ ) $l[] = bcadd($l[$x++], $l[$x]); endif; return $l; } 

Ruby

Recursive snippet

 def fib(num) num < 2 ? num : fib(num-1) + fib(num-2) end puts fib(10) 

The following Ruby code segments demonstrate how to calculate the Fibonacci sequence. Ruby is a reflective, object-oriented programming language. ...

Iterative snippet

 def fib(num) i, j = 0, 1 num.times { i, j = j, i + j } i end puts fib(10) 

Matrix Method One-Liner

 ruby -rmatrix -e 'puts (Matrix[[1,1],[1,0]]**(ARGV[0].to_i-1))[0,0]' 10 

Add to integer class

The (very fast) algorithm below adds a method to the Integer class:

 class Integer FibonacciComputer = Hash.new do |fibonacci, n| if fibonacci.has_key?(n - 1) and fibonacci.has_key?(n - 2) fibonacci[n] = fibonacci[n - 1] + fibonacci[n - 2] elsif fibonacci.has_key?(n + 1) and fibonacci.has_key?(n + 2) fibonacci[n] = fibonacci[n + 2] - fibonacci[n + 1] else half_n = n.div(2) case n.modulo(4) when 1 fibonacci[n] = (2*fibonacci[half_n] + fibonacci[half_n - 1])*(2*fibonacci[half_n] - fibonacci[half_n - 1]) + 2 when 3 fibonacci[n] = (2*fibonacci[half_n] + fibonacci[half_n - 1])*(2*fibonacci[half_n] - fibonacci[half_n - 1]) - 2 else fibonacci[n] = fibonacci[half_n]*(fibonacci[half_n] + 2*fibonacci[half_n - 1]) end end end FibonacciComputer[0] = 0 FibonacciComputer[1] = 1 FibonacciComputer.freeze def fib return FibonacciComputer.dup[self] end end puts (1..9).map{|i| i.fib}.join(", ") 

QBasic/VisualBasic

The following QBasic/Visual Basic code segments demonstrate how to calculate the Fibonacci sequence. The opening screen of QBasic 1. ... Visual Basic (VB) is an event driven programming language and associated development environment from Microsoft. ...

 n = 1 m = 1 FOR x = 1 TO 10 n = m o = m + n m = o n = o PRINT n NEXT x 

or

 x = 1 y = 1 FOR x = 1 to 100 z = x + y x = y y = z PRINT z + 1 NEXT x 

PL/SQL

The following PL/SQL code segment demonstrates how to calculate the Fibonacci sequence using iteration. PL/SQL (Procedural Language/Structured Query Language) is Oracle Corporations proprietary server-based procedural extension to the SQL database language. ...

Iterative snippet

 PROCEDURE fibonacci(lim NUMBER) IS fibupper NUMBER(38); fiblower NUMBER(38); fibnum NUMBER(38); i NUMBER(38); BEGIN fiblower := 0; fibupper := 1; fibnum := 1; FOR i IN 1 .. lim LOOP fibnum := fiblower + fibupper; fiblower := fibupper; fibupper := fibnum; DBMS_OUTPUT.PUT_LINE(fibnum); END LOOP; END; 

J

The following J code segments demonstrate how to calculate the Fibonacci sequence using double recursion, single recursion, iteration, power of phi, continued fraction, Taylor series, sum of binomial coefficients, matrix power, and operations in Q[√5] and Z[√5]. The J programming language, developed in the early 1990s by Ken Iverson and Roger Hui, is a synthesis of APL (also by Iverson) and the FP and FL functional programming languages created by John Backus (of FORTRAN, ALGOL, and BNF fame). ... As the degree of the Taylor series rises, it approaches the correct function. ...

All of the following J examples generate .

Double recursion

f0a and f0b use the basic identity . f0c uses a cache of previously computed values. f0d depends on the identity , whence and obtain by substituting n and n + 1 for k. Look up cache in Wiktionary, the free dictionary. ...

 f0a=: 3 : 'if. 1<y. do. (y.-2) +&f0a (y.-1) else. y. end.' 

 f0b=: (-&2 +&$: -&1) ^: (1&<) 

 F=: 0 1x f0c=: 3 : 0 if. y. >: #F do. F=: F,(1+y.-#F)$_1 end. if. 0 <: y.{F do. y.{F return. end. F=: F y.}~ t=. (y.-2) +&f0c (y.-1) t ) 

 f0d=: 3 : 0 if. 2 >: y. do. 1<.y. else. if. y. = 2*n=.<.y.%2 do. (n+1) -&*:&f0d n-1 else. (n+1) +&*:&f0d n end. end. ) 

Single recursion

 f1a=: 3 : 0 {. y. f1a 0 1x : if. *x. do. (x.-1) f1a +/|.y. else. y. end. ) 

 f1b=: {.@($:&0 1x) : ((<:@[ $: +/@|.@])^:(*@[)) 

Iteration

 f2=: 3 : '{. +/@|.^:y. 0 1x' 

Power of phi

Power of the golden ratio phi. Because of the limited precision of 64-bit IEEE floating-point numbers this method is good only for n up to 76. The golden section is a line segment sectioned into two according to the golden ratio. ... The IEEE Standard for Binary Floating-Point Arithmetic (IEEE 754) is the most widely-used standard for floating-point computation, and is followed by many CPU and FPU implementations. ...

 f3=: 3 : '<. 0.5 + (%:5) %~ (2 %~ 1+%:5)^y.' 

Continued fraction

The numerator of the continued fraction [0; 1, ..., 1] (with n 1's) as a rational number. In mathematics, a continued fraction is an expression such as where a0 is some integer and all the other numbers an are positive integers. ...

 f4=: {. @ (2&x:) @ ((+%)/) @ (0: , $&1x) 

Taylor series

Taylor series coefficients of and As the degree of the Taylor series rises, it approaches the correct function. ...

 f5a=: (0 1&p. % 1 _1 _1&p.) t. f5b=: (%-.-*:)t. 

 f5c=: (^@-: * 5&o.&.((-:%:5)&*)) t: 

Sum of binomial coefficients

The second variant below sums the back-diagonals of Pascal‘s triangle as a square upper triangular matrix. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 The first six rows of Pascals triangle In mathematics, Pascals triangle is a geometric arrangement of the binomial coefficients in a triangle. ...

 f6a=: i. +/ .! i.@- f6b=: [ { 0: , +//.@(!/~)@i. 

Matrix power

Computing the n-th power of the lower triangular unit matrix by repeated squaring. Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number. ...

 f7=: 3 : 0 x=. +/ .* {.{: x/ x~^:(I.|.#:y.) 2 2$0 1 1 1x ) 

Operations in Q[√5] and Z[√5]

Based on Binet’s formula In mathematics, the Fibonacci numbers form a sequence defined recursively by: That is, after two starting values, each number is the sum of the two preceding numbers. ...

operations are done in Q[√5] and Z[√5] with powers computed by repeated squaring. In mathematics, more specifically in abstract algebra, field extensions are the main object of study in field theory. ... Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number. ...

 times=: (1 5&(+/ .*)@:* , (+/ .* |.)) " 1 pow =: 4 : 'times/ 1 0 , times~^:(I.|.#:y.) x.' " 1 0 f8a =: {. @ (0 1r5&times) @ (-/) @ ((1r2 1r2,:1r2 _1r2)&pow) 

 f8b =: {:@(1 1x&pow) % 2x&^@<: 

Macromedia Flash Action Script

• Direct calculation

 function getFibonacci(_num:Number) { var _phi:Number = ((1+Math.sqrt(5))/2); return (Math.pow(_phi, _num)-Math.pow((1-_phi), _num))/Math.sqrt(5); //return (Math.pow(((1+Math.sqrt(5))/2), _num)-Math.pow((1-((1+Math.sqrt(5))/2)), _num))/Math.sqrt(5); } trace(getFibonacci(5)); 

• Recursive

 function getFibonacci(_num:Number) { if(_num < 2) return _num; return getFibonacci(_num-1)+getFibonacci(_num-2); } trace(getFibonacci(5)); 

TI-BASIC (Texas Instruments Graphing Calculators)

• Iterative

 :0→F :1→S :For(A,0,10) :Disp F :F+S→T :S→F :T→S :End 

Mathematica

The following Mathematica snippet demonstrates how to make a recursive implementation run faster by caching of intermediate results: This article is about computer software. ...

 fibonacci[0] = 0 fibonacci[1] = 1 fibonacci[n_] := fibonacci[n] = fibonacci[n-1] + fibonacci[n-2] 

Javascript

The following function returns the (n)th number within the sequence and is only accurate up to the 70th.

 function fibonacci(n) { var Phi=1.6180339887498948482; var fibonacciNumber=0; fibonacciNumber=Math.pow(Phi,n)/(Math.sqrt(5)); return Math.round(fibonacciNumber); } 

See also

• Fibonacci number
• Dynamic Programming
• Algorithms
• Optimizations
• Golden ratio
• Hello world program (A common first program for students.)

In mathematics, the Fibonacci numbers form a sequence defined recursively by: That is, after two starting values, each number is the sum of the two preceding numbers. ... In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below. ... Flowcharts are often used to represent algorithms. ... It has been suggested that Loop optimization be merged into this article or section. ... The golden section is a line segment sectioned into two according to the golden ratio. ... A hello world program is a software program that prints out Hello world! on a display device. ...

External links

• Fibonacci series implementations and benchmark
• More languages