A solution to this challenge: http://www.reddit.com/r/dailyprogrammer/comments/2zna5q/20140320_challenge_206_hard_recurrence_relations/

gistfile1.cpp

#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <limits>
#include <functional>
#include <utility>
#include <stdexcept>

using Number = double;
using NumberSequence = std::vector<Number>;
const Number NaN = std::numeric_limits<Number>::quiet_NaN();

class RecurrenceEvaluator
{
    using Instruction = std::function<void(void)>;
    using Program = std::vector<Instruction>;

    const Instruction _plus, _minus, _times, _divide;
    Program _program;
    NumberSequence _sequence, _stack;
    int _lastIndex;

    Number ExecuteProgram();
    Number Pop();
    template<typename F, bool isDivision=false> Instruction MakeBinaryOp();
    Instruction MakeConstant(Number c);
    Instruction MakeTap(int k);

public:
    RecurrenceEvaluator();
    void SetProgram(const std::string &programText);
    void SetInitialValue(const std::string &line);
    void ComputeValues(int lastIndex);
    Number GetValue(int i) const { return _sequence[i]; }
};

static std::string readline()
{
    std::string line;
    if (!std::getline(std::cin, line))
        throw std::runtime_error("input error");
    return std::move(line);
}

int main()
{
    using namespace std;

    RecurrenceEvaluator e;
    int n;

    try {
        string line;

        cout << "Enter expression:\n";
        line = readline();
        e.SetProgram(line);

        cout << "Enter initial values; finish with an empty line:\n";
        while (line = readline(), !line.empty())
            e.SetInitialValue(line);

        cout << "Enter count:\n";
        if (!(cin >> n) || n < 1)
            throw std::runtime_error("invalid count");

        e.ComputeValues(n);
    } catch (std::runtime_error &err) {
        cout << "Error reading input: " << err.what() << endl;
        return 1;
    }

    for (int i = 0; i <= n; ++i) {
        Number v = e.GetValue(i);
        if (v == v) // NaN?
            cout << i << ": " << v << endl;
    }

    return 0;
}

RecurrenceEvaluator::RecurrenceEvaluator() :
    _plus(MakeBinaryOp<std::plus<Number>>()),
    _minus(MakeBinaryOp<std::minus<Number>>()),
    _times(MakeBinaryOp<std::multiplies<Number>>()),
    _divide(MakeBinaryOp<std::divides<Number>, true>()),
    _lastIndex(-1)
{
    _sequence.reserve(4096);
    _stack.reserve(64);
}

void RecurrenceEvaluator::SetProgram(const std::string &programText)
{
    std::istringstream iss(programText);
    Number num;
    char ch;
    int tap;
    Number sign;

    while (iss >> ch)
    {
        switch (ch)
        {
        case '(':
            if (!(iss >> tap >> ch) || ch != ')')
                throw std::runtime_error("error parsing tap");
            _program.push_back(MakeTap(tap));
            break;
        case '+':
            _program.push_back(_plus);
            break;
        case '-':
            _program.push_back(_minus);
            break;
        case '*':
            _program.push_back(_times);
            break;
        case '/':
            _program.push_back(_divide);
            break;
        default:
            sign = ch == '~' ? -1 : 1;  // Use ~ for negative numbers to avoid ambiguity with subtraction
            if (ch != '~')
                iss.putback(ch);
            if (!(iss >> num))
                throw std::runtime_error("error parsing number");
            _program.push_back(MakeConstant(sign * num));
            break;
        }
    }

    if (_program.empty())
        throw std::runtime_error("empty program");
}

void RecurrenceEvaluator::SetInitialValue(const std::string &line)
{
    std::istringstream iss(line);
    int i;
    Number value;
    char ch;

    if (!(iss >> i >> ch >> value) || ch != ':')
        throw std::runtime_error("error parsing initial value");
    if (i < 0)
        throw std::runtime_error("invalid index for initial value");
    if (i >= _sequence.size())
        _sequence.resize(i + 1, NaN);
    if (i > _lastIndex)
        _lastIndex = i;

    _sequence[i] = value;
}

void RecurrenceEvaluator::ComputeValues(int lastIndex)
{
    if (_lastIndex+1 != _sequence.size())
        throw std::logic_error("internal error");

    while (++_lastIndex <= lastIndex)
        _sequence.push_back(ExecuteProgram());
}

Number RecurrenceEvaluator::ExecuteProgram()
{
    for (auto& insn : _program)
        insn();
    return Pop();
}

Number RecurrenceEvaluator::Pop()
{
    if (_stack.empty())
        throw std::runtime_error("empty stack");

    Number n = _stack.back();
    _stack.pop_back();
    return n;
}

template<typename F, bool isDivision>
RecurrenceEvaluator::Instruction RecurrenceEvaluator::MakeBinaryOp()
{
    F f;

    return [=]() {
        Number y = Pop(), x = Pop();
        
        if (isDivision && y == 0)
            _stack.push_back(NaN);
        else
            _stack.push_back(f(x, y));
    };
}

RecurrenceEvaluator::Instruction RecurrenceEvaluator::MakeConstant(Number c)
{
    return [=]() { _stack.push_back(c); };
}

RecurrenceEvaluator::Instruction RecurrenceEvaluator::MakeTap(int k)
{
    if (k <= 0)
        throw std::runtime_error("invalid tap index");

    return [=](){
        if (_lastIndex - k < 0)
            _stack.push_back(NaN);
        else
            _stack.push_back(_sequence[_lastIndex - k]);
    };
}