Fibonacci numbers (sh)

From LiteratePrograms
Jump to: navigation, search
Other implementations: bc | C | C Plus Plus templates | dc | E | Erlang | FORTRAN | Haskell | Icon | Java | JavaScript | Lisp | Lua | occam | Oz | PIR | Prolog | Python | Sed | sh | sh, iterative | 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


 F(n) =
 \begin{cases}
   0             & n = 0 \\
   1             & n = 1 \\
   F(n-1)+F(n-2) & n > 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

[edit] 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
}

[edit] 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
hijacker
hijacker
hijacker
hijacker