C++

/*//////////////////////////////////////////////////////////////////
Difference Equation Sequence Program
--------------------------
Uses recursion to find a requested term in a sequence defined
by a difference equation.
Seems to hit about 4300 recursions at once before stack overflow.
/////////////////////////////////////////////////////////////////*/

//Input/Output header
#include <iostream>

//allows us to use cout and cin without prepending std namespace
using std::cout;
using std::cin;

//declaration for data concerning each term
struct TERM {
    static float a, b;            //static values defining the co-efficients in the sequence
    float val;                    //the value of this term
    TERM *next;                    //the next item in the linked-list
};

//declare our static variables so they're global
float TERM::a, TERM::b;

//our base term structure
TERM *seq;

//attempts to retrieve a specified item in the list
TERM *getItem(int pos) {
    TERM *cdtr = seq;        //declare a conductor set to our base term
    int n = 0;                //number of items we've traversed

    //continue while our no. items traversed is less than desired number
    while (n < pos) {
        //check if there's another item ahead
        if (cdtr->next != NULL) {
            cdtr = cdtr->next;        //if so, move onto it and increment n
            n++;
        }else {
            return NULL;    //otherwise, we've reached the end before our desired number, so return a NULL value
        }
    }

    //if we get here, it means we retrieved the item succesfully, so return it
    return cdtr;
}

//adds a term to the end of our list
TERM *addTerm() {
    TERM *cdtr = seq;        //declare and initialise our conductor

    //while there's any items ahead, keep moving on
    while (cdtr->next != NULL) {
        cdtr = cdtr->next;
    }
    //once we reach the end, make our next item a new term
    cdtr->next = new TERM;
    cdtr = cdtr->next;            //move cdtr to the new item
    cdtr->next = NULL;            //make sure our next item is set to NULL

    return cdtr;                //return the new item
}

//attempts to find a specified term in our sequence
float getTerm(int pos) {
    TERM *t = getItem(pos);            //our desired term
    TERM *prev = getItem(pos - 1);    //the term previous to this one

    //check whether or not our term already exists
    if (t == NULL) {
        //check if our previous term exists
        if (prev == NULL) {
            //if not, retrieve the term below ours- will recurse until any starting point is found
            if (getTerm(pos - 1) == 0) {    //check to make sure the call succeeded
                return 0;
            }

            prev = getItem(pos - 1);        //re-set our previous term to the item that should now exist
        }
        //check if our attempt to add a new term succeeds
        if ((t = addTerm()) == NULL) {
            return 0;
        }
        //calculate the new value based off our previous term and return it
        t->val = (prev->val * prev->a) + prev->b;
        return t->val;
    }else {
        return t->val;        //if our current term already exists, just return it
    }
}

//will delete all items from a specified item onwards
void deleteItem(int pos) {
    TERM *cdtr = getItem(pos);        //retrieve the item of our specified position

    //if there's any items ahead of us, delete it- should recurse until it reaches the end of the list
    if (cdtr->next != NULL) {
        deleteItem(pos + 1);
    }
    delete cdtr;    //delete our current item, all items ahead should now be cleared
}

//entry point
int main() {
    seq = new TERM;                        //initialise our base term
    seq->next = NULL;
    seq->val = 0;                        //starting value
    seq->a = 1.0f; seq->b = 1.0f;        //a is the no. by which we multiply; b the value we add

    cout << getTerm(4000) << "\n";            //output our desired term
    deleteItem(0);                            //delete the data we've created
    cout << "Done.";                        //output a finishing message
    cin.get();                                //wait until a keypress to exit

    return 0;                                //exit
}