Fibonacci Series w/Templating technique

Alex Edwards 0 120 Views

Nothing too special, but it was an interesting task.

#include <cstdlib>
#include <iostream>
#include <vector>
#define VALUE_ 12
using namespace std;

/**
Fibonacci series using template recursion -- successful
*/

class Fibonacci{
     private:
             vector<bool> analyzed;
             bool start;
             unsigned short current, firstN;

     public:
            Fibonacci(): analyzed(0), current(0), start(false) {};
            template<unsigned short N>
            inline unsigned short series(){
                if(!start){
                     start = true;
                     vector<bool> tempVector(N, false);
                      analyzed = tempVector;
                     (firstN = N);
                }
                if(analyzed[N] == false){
                    analyzed[N] = true;
                    if((this->series<N>() <= firstN)){
                        cout << (this->series<N>()) << " " << flush;
                    }
                }
                if(N%2 == 0)
                       return(this->series<N - 2>() + ((this->series<N - 1>())));
                else return (this->series<N - 1>() + ((this->series<N - 2>())));
            }

            static void reset(Fibonacci &fib){
                   fib.start = false;
            }
};

template<>
inline unsigned short Fibonacci::series<1>(){
    if(analyzed[1] == false){
          analyzed[1] = true;
          cout << 1 << " " << flush;
    }
    return 1;
};

template<>
inline unsigned short Fibonacci::series<0>(){
    if(analyzed[0] == false){
          analyzed[0] = true;
          cout << 0 << " " << flush;
    }
    return 0;
};

#ifdef NUM
#undef NUM
#define NUM VALUE_
#else
#define NUM VALUE_
#endif

int main(int argc, char *argv[]){
    Fibonacci fib;
    fib.series<NUM>(); //prints out the entire series up to N
    Fibonacci::reset(fib);
    cout << endl;
    fib.series<NUM - 6>();
    cin.get();

#undef NUM
#undef VALUE_

    return 0;
}

Dani AI

Generated

— nice little exercise. The template-recursive approach is an interesting idea, but the implementation has a few correctness and design problems that make it fragile and undefined on typical compilers.

Two concrete issues to look at: the boolean buffer is created with N elements but the code indexes analyzed[N], which is out-of-range (valid indices are 0..N-1) and is undefined behavior. Also, calling series<N>() from inside the body of series<N>() is a direct self-call that never decreases N and therefore never reaches the base specializations — this produces infinite recursion rather than the intended compile-time-style recursion. A couple of other fragile choices: std::vector<bool> is a packed-proxy specialization (not a normal bool array), the reset helper only flips the start flag without clearing other state, and using unsigned short will overflow quickly for larger Fibonacci indices.

A simpler, safer runtime approach is to compute and print iteratively (no templates, no UB, and trivial to reason about):

#include <iostream>
#include <cstdint>

constexpr unsigned N = 12;

int main() {
    std::uint64_t a = 0, b = 1;
    std::cout << a;
    for (unsigned i = 1; i <= N; ++i) {
        std::cout << ' ' << b;
        auto next = a + b;
        a = b;
        b = next;
    }
    std::cout << '\n';
}

If the goal is compile-time computation, prefer a pure template metaprogram or a constexpr function (not mixing template instantiations with runtime state). Also use constexpr variables instead of macros, allocate any memo buffers with N+1 elements (or std::array/std::bitset when size is compile-time), and pick a wide integer type: on common platforms unsigned short overflows at F(25) (use std::uint64_t to be safe up to F(93), or a big-integer library for larger indices).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview