Fibonacci numbers (sh)
From LiteratePrograms
- Other implementations: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript | Python | Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | Visual Basic .NET
The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by
- 1 \\ \end{cases} ."/>
Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.
The fibonacci numbers in Bourne Shell:
<<fib.sh>>= #!/bin/sh fib main
Implementation
This is a recursive implmentation.
<<fib>>= fib () { n=$1
The numbers 0 and 1 are returned unchanged on the standard output pipe
<<fib>>= if test $n -lt 2 ;then echo "$n"
We use bc to perform the actual calculations.
echo produces the input to bc via a pipe. The backticks tells the shell to execute the contained shell command and replace itself with the output from that execution. The $() operator does the same thing.
What we do here is executing echo $n-1 | bc and then execute fib (first execution's output), concatenate it with + and the same trick for $n-2. The result is then piped in to bc, which will produce the result on the standard output pipe.
<<fib>>= else echo "`fib $(echo $n-1 | bc)`+`fib $(echo $n-2 | bc)`" | bc fi }
Test driver
When this test code is run, the output should be:
fib 1 = 1
fib 2 = 1
fib 3 = 2
fib 4 = 3
fib 5 = 5
fib 6 = 8
fib 7 = 13
fib 8 = 21
fib 9 = 34
fib 10 = 55
<<main>>= for n in 1 2 3 4 5 6 7 8 9 10; do echo "fib $n = `fib $n`" done
| Download code |