Two Fibonacci functions

Question

These are two of tasks, which I had to do for the recruitment process to be started in some company. Unfortunately they didn't like it so I've decided to share it here for discussion.

1. Add up all the even elements of the Fibonacci sequence below 1000. In my solution it is a method fibSumEven.

2. Write a recursive function that calculates the Fibonacci sequence up to 1000. In my solution it is a method fibR.

Fibonacci.h

#ifndef FIBONACCI_H_
#define FIBONACCI_H_

#include <iostream>
#include <string>
#include <sstream>

class CFibonacci
{

private:

    // Recursive function that calculates the Fibonacci sequence up to given LIMIT
    // limit - The limit, up to which sequence numbers will be calculated
    static int fibHelper(int limit, int x1, int x2)
    {
        int x = x1 + x2;
        if(x <= limit)
        {
            return fibHelper(limit, x2, x);
        }
        return x2;
    }

public:

    // A caller to recursive Fibonacci sequence up to given limit
    static int fibR(int limit = 1000)
    {
        if(limit <= 0)
        {
            return 0;
        }
        return fibHelper(limit, 0, 1);
    }

    //Adds up all the even elements of the Fibonacci sequence below limit
    static int fibSumEven(int limit=1000)
    {
        int x1 = 0, x2 = 1, x = 0, sum = 0;
        while(x <= limit)
        {
            x = x1 + x2;
            if(x % 2 == 0)
            {
                sum += x;
            }
            x1 = x2;
            x2 = x;
        }
        return sum;
    }
};

#endif /* FIBONACCI_H_ */

There was a disclaimer:

Considering the ith element of the Fibonacci sequence Fib(i) = x, the element x is a natural number and is itself bounded by the value 1000 and not all the elements to Fib(1000).

Why could the solution have been disliked by the recruiters?

Answer 1

I don't like how you have all your logic in the header file. You should declare your methods and fields in the header and use the .cpp file for logic.

On the other hand, C++ is not strictly object oriented, the way C# and Java are. You didn't need a class for this solution, you could just have called fibHelper() from main().

Third point is your naming. fibHelper() actually isn't a helper function, it is the function that actually calculates the Fibonacci sequence. fibR() actually isn't recursive, like your comment says, it calls the recursive function. int x1 doesn't say what it actually does, although it is easy to guess because the program is only a couple lines long - in a large project, this could (and probably would) cause many weeks of time wasted catching bugs.

Fourth is consistency:

static int fibR(int limit = 1000)
static int fibSumEven(int limit=1000)

For the most part, you are consistent, and I like how you use spaces around your operators and braces on your one-line ifs.

Answer 2

• Break down the requirements of a problem

Take your time, break down the components of a question, define anything that isn't clear, and ask questions if you are confused by anything.

Problem 1 bounds the sequence with a threshold below 1000 (non-inclusive). Your solution treats the threshold as an inclusive value. The problem wouldn't be seen because 1000 isn't a Fibonacci number, but if the problem included a Fibonacci value for a threshold, you would process and include an extra value.

Problem 2 asks that you return the Fibonacci sequence and the threshold is up to 1000. I would actually ask for clarification on that, as up to could mean inclusive or non-inclusive. Your solution implements the threshold as inclusive and this may not be right. Also, you return the max Fibonacci value below the threshold instead of the sequence. Your recruiter was likely looking for tail-call recursion, which is implemented. Unfortunately, other issues caused them to dislike the result.

• Look for opportunities to reuse code

Instead of writing 2 separate functions to do the same task, you could split the problem into components that provided the facilities to generate outputs or be used as inputs into other systems. For this problem, you could write an RecurringSequenceIterator that maintained the state of the recurring values and the relation between those values. The recurrence relation for generating all Fibonacci's is next_fib = curr_fib + prev_fib and for Even Fibonacci's is next_even_fib = 4 * curr_even_fib + prev_even_fib. Pass these as functors into your iterator and you have a general purpose solution for generating the values of a recurring sequence.

With a recurring sequence generator, you can use one of the standard insert iterators to create a sequence up to a threshold for problem 2. It also lends itself to range construction in containers if you know the start and end range of your Fibonacci's.

• Use Templates to make generalized and reusable code

You've hard-coded the integral type into your function, resulting in a function that is only capable of counting up to Fib(46) before overflowing. uint32_t can calculate to Fib(47), int64_t to Fib(92), and uint64_t to Fib(93). Perhaps I want to calculate some Fibonacci number that requires a 256-bit number. Templates provide a general purpose solution that isn't dependent on a specific type.

• Write appropriate tests

Verify that your code does what is supposed to. Provide functions with inputs that have known outputs and compare those results. Since you only provided the Fibonacci header and no test function, I won't comment on this further.

• Pick up a coding standard

Where ever you end up working, you'll be using their coding guidelines. Until then, you should be using something that fixes many of the basic problems. Keep in mind that coding standards are designed specifically for the needs of a company. Google, JSF, LLVM, Boost, Microsoft (book) all offer coding standards/guidelines/style guides based on the needs of their respective organization.

• Organize your #includes

Most coding standards will sort libraries by reliability then name. Some coding standards address conditional includes as well.

• #include only what you need

Every time you #include a library, you are increasing the compile time of a project. In your header, <iostream>, <sstream>, and <string> are not used anywhere inside your Fibonacci library.

• Use constexpr/const where it makes sense

const provides a correctness mechanism in which your function is limited in what it can do, whether it is modifying a variable or object state. It also provides compile-time type-checking, allowing you to catch errors much earlier (also allows the compiler to possibly make optimizations). Since it is apparent you are still coding using c++03, constexpr doesn't exist. However, you should get used to using it with c++11 and later.

Consider your code:

static int fibHelper(int limit, int x1, int x2) {...}

limit, x1, x2 are values that do not change in the local function. Qualify them as const.

static int fibHelper(int const limit, int const x1, int const x2) {...}

• Use meaningful names

x, x1, x2 projects an order, but as someone who may have glossed over your code, I could interpret the ordering as x, x1, x2. Better naming would allow you to enforce the ordering, such as using next_fib, prev_fib, curr_fib to reflect an ordering of prev_fib, curr_fib, next_fib.

Answer 3

I think the main problems of your solutions are the following.

1. For the fibR and fibHelper functions, you have the parameter limit in the recursive function which is passed unaltered during the recursive calls. This is not good practice, since it needlessly occupies space on the stack. Moreover, the specification (at least as reported by the Asker) says:

   Write a recursive function that calculates the Fibonacci sequence up to 1000.

   but the function fibR only returns the last value.

2. The major problem is in the function fibSumEven that sums all the even elements, since it calculates an incorrect value. The reason is that the test for limit is done after the value of x is calculated and, if even, summed to the result. So, for certain values of limit, the next Fibonacci number is incorrectly summed up. Note that, in the particular case of limit = 1000, the result is correct, but, for instance, it is not correct in the case limit = 6.

Answer 4

1. Should be while(x < limit)

2. Iteration of x should not occur between the limit check on x and adding it to sum (you can and will, in general, add values of x to sum which would not pass the limit check).

3. fibR does not return a sequence (i.e. array).

4. Most importantly I think, you have implemented the calculation of the fibonacci sequence twice. fibSumEven should delegate its iterating work on x to the helper function. It makes code more maintainable to keep each task delegated to a unique method.

You might consider reducing the fibonacci sequence generation to some initializing and iterating functions. This way, all of the actual calculation can be handled by a dedicated class:

class FibCalculator 
{

    private:    
        //Index starting at zero to keep with programming etiquette.
        static int seqIndex = 0;
        static int currValue = 1;
        static int lastValue = 0;
    public:
        static void iterate() {
            seqIndex++;
            currValue = lastValue + (lastValue = currValue);
        }
        static void reset() {
            seqIndex = 0;
            currValue = 1;
            lastValue = 0;
        }
        static int getIndex() const {
            return seqIndex;
        }
        static int getValue() const {
            return currValue;
        }
}

Any logistical things one wishes to do with the fibonacci sequence (i.e. sum the even values up to but not including 1000) can be done by invoking this class' methods.