7
$\begingroup$

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

$\endgroup$

migrated from programmers.stackexchange.com Aug 7 '12 at 20:19

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • 1
    $\begingroup$ What does "definitive for loop" mean? $\endgroup$ – Keith Thompson Aug 7 '12 at 20:23
  • $\begingroup$ Basically a counted loop. Eg, I take the nth term as input and say for i in range(input): $\endgroup$ – qzxt Aug 7 '12 at 20:26
  • $\begingroup$ I could remove if statements by moving the conditional expressions to for loops but that'd be just a completely useless hack, IMHO. $\endgroup$ – toniedzwiedz Aug 7 '12 at 20:59
  • $\begingroup$ So I'm not crazy, then, and there really isn't away to do this without conditionals? $\endgroup$ – qzxt Aug 7 '12 at 21:01
  • $\begingroup$ @qzxt not if you want to catch invalid input, no. $\endgroup$ – toniedzwiedz Aug 7 '12 at 21:04
10
$\begingroup$

If you only have to use a for loop that iterates until it finds the n-th Fibonacci number, you could use something like this:

int fib(int n)
{
    int p = 0;
    int c = 1;
    int r = 0; // The result is initialized to 0 (undefined). 
    for (int i = 0; i < n; i++)
    {
        r = p + c; // Produce next number in the sequence.
        p = c;     // Save previous number.
        c = r;     // Save current number.
    }

    return r;
}

NOTE

In the solution above, I assume that the Fibonacci sequence is 1 1 2 3 5 8 13 ... and that n has the range 1, 2, 3, ... Since under these assumptions there is no Fibonacci number for n < 1, the function returns a 0 for n < 1 to indicate that the input parameter is out of range (see Tom's suggestions in the comments below).

$\endgroup$
  • $\begingroup$ Output for 0 should be 0, otherwise, a good, simple and concise answer. $\endgroup$ – toniedzwiedz Aug 7 '12 at 21:10
  • $\begingroup$ It depends on how you count, actually fib should be undefined for n < 1. Or do you mean that 0 represents undefined, and therefore fib(n) should return 0 for all n < 1? $\endgroup$ – Giorgio Aug 7 '12 at 21:13
  • $\begingroup$ That's true, it depends. If we include 0, the output should be 0. If we exclude it, the function should return a special value to indicate invalid input, which should be done for negative numbers as well... but the OP doesn't accept conditional expressions, much less throwing exceptions so I guess it's fine the way it is. $\endgroup$ – toniedzwiedz Aug 7 '12 at 21:18
  • 2
    $\begingroup$ @Giorgio Mathematically, the Fibonacci sequence is perfectly well-defined for $n\lt 0$; there's nothing that prevents you from running the sequence backwards, inverting $f_{n+1}=f_n+f_{n-1}$ to get $f_{n-1} = f_{n+1}-f_n$ - or, defining $g_n=f_{-n}$, $g_{n+1} = g_{n-1}-g_n$. $\endgroup$ – Steven Stadnicki Mar 6 '13 at 17:40
10
$\begingroup$

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 & n = 0\\ 1 & n = 1\\ F_{n-1} + F_{n - 2} & \text{otherwise} \end{cases}$$

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

def fib(n):
    if n < 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)! fibtree

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". fib2

def fib2(n):
    if n < 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 < 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
$\endgroup$
  • 2
    $\begingroup$ Wow, great answer! Note that bringing this into a form compatible with primitive recursion -- that is, counting down in common definitions -- is easy by using $n-i$ inside the (counting-down) loop. $\endgroup$ – Raphael Aug 8 '12 at 7:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.