# Find Nth Fibonacci Number

**Daily Coding Problem: Problem #1790 [Easy]**

Implement the function `fib(n)`

,
which returns the n^{th} number in the Fibonacci sequence,
using only `O(1)`

space.

## Analysis

The “using only `O(1)`

space” stipulation is important.
It means you’re supposed to use only a fixed number of variables
in calculating the n^{th} Fibonacci number.

The usual definition of Fibonacci number F_{n} is almost a
definition of a primitive recursive function:

F_{n} = F_{n-1} + F_{n-2}

F_{0} = 0

F_{1} = 1

This invites a recursive function:

```
func fib(n int) int {
if n == 1 { return 1 }
if n == 0 { return 0 }
return fib(n-1) + fib(n-2)
}
```

The function above looks like it uses only the formal argument `n`

,
which is a fixed number of variables.
I don’t think that’s what the interviewer wants here.
Each function call ends up causing the allocation and use of a “stack frame”,
some amount of memory to hold formal arguments,
where in the program to resume execution when a function returns,
and keep track of the value of `fib(n-1)`

while the computer calculates `fib(n-2)`

.

Here’s a non-recursive version of `fib(n)`

:

```
func fib(n int) int {
x, y := 0, 1
for i := 0; i < n; i++ {
t := x + y
x,y = y,t
}
return x
}
```

Only 5 integers worth of working storage, plus a single stack frame since it does not recurse or call any other functions.

I was amused to find that
you can’t write the body of the for-loop with a single assignment
like `t, x, y = x+y, y, t`

and get correct answers.

## This Problem in Job Interviews

At face value, this is a very simple coding problem meriting the “[Easy]” rating.

I reckon that most job candidates have fiddled with
Fibonacci numbers and the sequence
in a way that makes the `O(1)`

extra space version the natural version to write.
I recall producing the Fibonacci Sequence
on a simple electronic calculator that had one “memory” location
by a repetitious series of three or four key presses.
Additionally, specifying `O(1)`

space means the interviewer doesn’t get
to see if the job candidate understands recursion.

These observations make the problem seem flawed.

It’s possible that an interviewer could use this problem as one of several questions in an interview. I’d suggest asking for a recursive version after doing this one, and asking for memoizing the recursive version after that. Not all coding problems could be used in this fashion. Some coding problems have an explicit “What about” extra question, “what about finding a palindrome doubly-linked list?” for example.

I wonder if the point of the problem is to get at the job candidate’s
knowledge of language implementation details.
This problem could be a jumping off pointer for discussion of
stack frames, scopes of variables,
the differences between formal arguments and local variables,
and even comp sci theory, like recursion can be implemented via iteration
and vice versa.
This would have been a great problem for the *Daily Coding Problem* book,
if the authors of that book had bothered to include any discussion about
alternatives, or why the phrasing of the problem matters.

Thinking about this question from the viewpoint of an interviewer reveals faults in the grinding leetcode approach to coding problems. An interviewer uses coding problems to get insight into what a job candidate has to offer in many areas, code quality, imagination, depth of comp sci knowledge, writing testable code, program design, communication skills. If you solve a leetcode problem by getting a single solution, you’re missing out on practicing all those areas.