Substitution cipher algorithm performance boost This algorithm is meant to read a string of numbers on an input, a naive substitution cipher code (A = 1, B = 2, ..., Z = 26) and output the number of ways the code could be interpreted (e.g. 25114 could mean 'BEAN', ‘BEAAD’, ‘YAAD’, ‘YAN’, ‘YKD’ and ‘BEKD’, hence output is 6). 

It is working properly, but not fast enough, though.  Is there a way to improve its performance? I commented it heavily, so it is easy to read.

#include &lt;iostream&gt;
#include &lt;string&gt;

using namespace std;

//Those are global, because handled by both functions
int ways;       //number of ways the code could be interpreted
string s;       //input

//Takes account of all the tuples after the one on position "start" using
//recursion
void findNextPossible(size_t start) {
    if(start + 2 &lt;= s.length()){
        //Tuple considered
        string ss = s.substr(start, 2);
        //Otherwise not interpretable as a letter
        if(ss &lt;= "26") {
            ways++;
            for(size_t i = 0; i &lt;= s.length(); i++) findNextPossible(start+2+i);
        }
    }
}

int main() {
    size_t pos;
    bool test, someDeletedInTheMiddle;
    //Until zero on input
    while(cin &gt;&gt; s, s.at(0) != '0') {
        ways = 0;
        test = true;
        someDeletedInTheMiddle = false;
        pos = s.find('0');
        //In this while I look for zeros
        while(pos != string::npos) {
            //Code with 30,40,... is not valid -&gt; output 0
            if(s.at(pos - 1) &gt; '2') {
                test = false;
                break;
            }
            //If delete some in the middle, output smaller by 1
            if((pos &gt;= 2 &amp;&amp; pos &lt; s.length()-1) &amp;&amp; s.length() &gt; 2) someDeletedInTheMiddle = true;
            //Don't cosider the tuple with zero in it anymore
            s.erase(pos-1, 2);
            //Any other zero?
            pos = s.find('0', pos);
        }
        if(test) {
            if(!someDeletedInTheMiddle) ways++;
            //Process the rest
            for(size_t i = 0; i &lt; s.length(); i++) {
                findNextPossible(i);
            }
        }       
        cout &lt;&lt; ways &lt;&lt; endl;
    }
    return 0;
}
You should use memoization on findNextPossible(), otherwise your algorithm has exponential complexity.

Also: the optimization obtained by looking for '0's will be no more useful once you use memoization... so the resulting code should become much, much smaller.

This is a possible implementation:

#include &lt;string&gt;
#include &lt;map&gt;
#include &lt;iostream&gt;
#include &lt;cassert&gt;

using namespace std;

int ways(std::string s) {
  static map&lt;string,int&gt; cache;
  map&lt;string,int&gt;::const_iterator f = cache.find(s);
  if (f!=cache.end()) return f-&gt;second;
  //  cout&lt;&lt;"ways("&lt;&lt;s&lt;&lt;")"&lt;&lt;endl;                                                                                                            
  if (s.size()==0) return 1;
  if (s[0]=='0') return 0; // no way the first digit is 0                                                                                     
  if (!isdigit(s[0])) return 0;
  if (s.size()==1) return 1; // only one possibility for a single digit                                                                       
  // here we have at least 2 digits                                                                                                           
  if (!isdigit(s[1])) return 0;
  int n = 10*(s[0]-'0')+(s[1]-'0');
  if (n&gt;26) return cache[s] = ways(s.substr(1)); // cannot merge first two digits.                                                                       
  return cache[s] = ways(s.substr(1)) + ways(s.substr(2)); // two possible interpretations                                                               
}

const char *tests[]={"1213","12","214","205",0};

int main() {
  for (int i = 0; tests[i]; ++i) {
    cout&lt;&lt;tests[i]&lt;&lt;": "&lt;&lt;ways(tests[i])&lt;&lt;endl;
  }
}