Is it possible to find the nth term  of a Fibonacci sequence using a definitive for loop? I'm using the book Introduction to Computer Science by John Zelle and at the end of Chapter 3 (Computing with numbers), I'm asked to find the nth term of a Fibonacci sequence presumably using a definitive for loop, as no other decision structure has been introduced yet. 

Is this possible? I've tried everything I could think of.

**I know how to solve it using if statements and such. But the book hasn't yet covered decision structures, yet it asks me to find the nth term(given by the user). So I can only presume to know how to do this using "for" loops as this is all that has been covered so far
If it is only the third chapter, I doubt the authors have covered dynamic programming, but I will illustrate what is going on when a for loop is used to compute the $n^\text{th}$ Fibonacci number, $F_n$.

Recall the definition, 
$$F_n = \begin{cases} 0 &amp; n = 0\\
1 &amp; n = 1\\
F_{n-1} + F_{n - 2} &amp; \text{otherwise}
\end{cases}$$

We could naively compute this using a recursive function defined in Python as,

def fib(n):
    if n &lt; 2:
        return n
    else:
        return fib(n - 1) + fib(n - 2)


However by recomputing the same sub-problem many times, this function requires exponential time to compute (illustrated below)! 


There is a fix, though. We can use dynamic programming to do "smarter" recursion and keep our previous results around. This way, we don't need to recompute $F_i$. Our function call "tree" will collapse to a list and and will compute $F_n$ from the "bottom-up".


def fib2(n):
    if n &lt; 2:
        return n
    else:
        if not results[n]:
            results[n] = fib2(n - 1) + fib2(n - 2)
        return results[n]


Now we have our $O(n)$ time algorithm to compute $F_n$, but if you notice, we require $O(n)$ additional space (one spot in the array for each $F_i$). This can be cut down to $O(1)$ additional space because each $F_i$ requires only two other fibonacci numbers, namely $F_{i-1}$ and $F_{i-2}$. 

def fib3(n):
    if n &lt; 2:
        return n
    f_0 = 0
    f_1 = 1
    f_n = 0
    for _ in range(n - 1):
        f_n = f_0 + f_1
        f_0 = f_1
        f_1 = f_n


    return f_n