index
| submit
| rank
| book

## fibonacci – The Fibonacci Sequence

Write a program that computes numbers in the fibonacci sequence.
This sequence is defined recursively as follows:

- F₀ = 0
- F₁ = 1
- Fₙ = Fₙ₋₁ + Fₙ₋₂

That is, the zeroth Fibonacci number is zero and the first Fibonacci number is one.
Other Fibonacci numbers are given by the sum of its two predecessors.

The first 10 numbers in the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21 and 34.

### Input and output

Input will consist of several lines,
each with a single integer *n*
indicating the position in the Fibonacci sequence.

For each line of input,
output should contain a line
with a corresponding number *Fₙ*
indicating the Fibonacci number in position *n*.

### The `fibonacci`

function

Your program should contain a `fibonacci`

function
that takes an integer and returns an integer.
Please refer to the information for your chosen language:

- C prototype:
`int fibonacci(int n)`

- Haskell type:
`fibonacci :: Int -> Int`

- Python definition:
`def fibonacci(n):`

- C++ prototype:
`int fibonacci(int n)`

Your function is expected to have good performance.
The maximum expected complexity is *O(n)*.

### Scoring

- 1/6: works for the above example albeit in an incorrect format
- 2/6: works for the above example in the correct format
- 3/6: works for other examples
- 4/6: has good performance
- 5/6: works for edge cases
- 6/6: implements the
`fibonacci`

function

try first: factorial fibonacci1

try next: index-string

index
| submit
| rank
| book

Copyright © 2020-2021 Rudy Matela

All rights reserved