Fibonacci sequence: Difference between revisions
(Befunge ftw!) |
|||
Line 33: | Line 33: | ||
END IF |
END IF |
||
END FUNCTION</qbasic> |
END FUNCTION</qbasic> |
||
=={{header|Befunge}}== |
|||
00:.1:.>:"@"8**++\1+:67+`#@_v |
|||
^ .:\/*8"@"\%*8"@":\ < |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
Revision as of 02:08, 1 March 2008
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
The Fibonacci sequence is a sequence of numbers defined as such:
Where n is an integer greater than 2: F1 = F2 = 1 Fn = Fn-1 + Fn-2
Write a function to generate the nth Fibonacci number. Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).
BASIC
Iterative
<qbasic>FUNCTION itFib (n) IF (n <= 2) THEN
itFib = 1
ELSE
ans = 0 n1 = 1 n2 = 1 n = n - 2 DO WHILE (n > 0) ans = n1 + n2 n1 = n2 n2 = ans n = n - 1 LOOP itFib = ans
END IF END FUNCTION</qbasic>
Recursive
<qbasic>FUNCTION recFib (n) IF (n <= 2) THEN
recFib = 1
ELSE
recFib = recFib(n - 1) + recFib(n - 2)
END IF END FUNCTION</qbasic>
Befunge
00:.1:.>:"@"8**++\1+:67+`#@_v ^ .:\/*8"@"\%*8"@":\ <
Forth
: fib ( n -- fib ) 0 1 rot 0 ?do over + swap loop drop ;
Java
Iterative
<java>public static long itFibN(int n){ if(n <= 2)return 1; long ans = 0; long n1 = 1; long n2 = 1; for(n -= 2;n > 0;n--){ ans = n1 + n2; n1 = n2; n2 = ans; } return ans; }</java>
Recursive
<java>public static long recFibN(int n){ if(n <= 2) return 1; return recFibN(n-1) + recFibN(n-2); }</java>
MAXScript
Iterative
fn fibIter n = ( if n <= 2 then ( 1 ) else ( fib = 1 fibPrev = 1 for num in 3 to n do ( temp = fib fib += fibPrev fibPrev = temp ) fib ) )
Recursive
fn fibRec n = ( if n <= 2 then ( 1 ) else ( fibRec (n - 1) + fibRec (n - 2) ) )
Python
Iterative
<python>def fibIter(n):
if n <= 2: return 1 fibPrev = 1 fib = 1 for num in xrange(2, n): temp = fib fib += fibPrev fibPrev = temp return fib</python>
Recursive
<python>def fibRec(n):
if n <= 2: return 1 else: return fibRec(n-1) + fibRec(n-2)</python>