# 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/shfib 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>>=iftest $n -lt 2 ;thenecho "$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>>=elseecho "`fib $(echo $n-1 | bc)`+`fib $(echo $n-2 | bc)`" | bcfi}

## 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>>=forn in 1 2 3 4 5 6 7 8 9 10;doecho "fib $n = `fib $n`"done

Download code |