私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ボタンを押して数を作ろう」（CodeIQ）を参照してください。
次のように1行でパラメータが入力されます。
初期値を1として×2と+1だけを組み合わせた場合、最小何回の計算で入力値になるかを求めよ、という問題です。
C言語で解答しています。
#include <stdio.h>
void calcProcess(unsigned long input){
unsigned long add1 = 0; // 1を足した回数
unsigned long mlt2 = 0; // 2をかけた回数
unsigned long now = input;
while(now > 1){
if(now % 2){
now -= 1;
add1 += 1;
}
else{
now /= 2;
mlt2 += 1;
}
}
printf("%ld\n", add1 + mlt2);
}
int main(int argc, char* argv[]){
unsigned long input = 0;
char str[256] = {0};
while( fgets(str, sizeof(str), stdin) != NULL ){
sscanf(str, "%lu", &input);
calcProcess(input);
}
return 0;
}
この問題は入力値から初めて÷2と-1を組み合わせて1にする回数を求めるのと同じ、ということにさえ気づけば簡単な問題です。
考え方は次の通りです。
（5の場合）
5-1=4、4/2=2、2/2=1、で3回です。
確認のため逆に計算してみます。
1*2=2、2*2=4、4+1=5で1から始めて3回で5になります。
（26の場合）
26/2=13、13-1=12、12/2=6、6/2=3、3-1=2、2/2=1、で6回です。
calcProcess()で上記の処理をやっています。
再帰でも実装できますが、ループで処理しています。
元のプログラムでカウントをadd1とmlt2に分けているのはデバッグ時にわかりやすいためです。引数inputをnowに代入し直しているのも引数の値を変更したくなかっただけでそのまま使用しても構いません。
そしてwhiteループではなくforループで書くともっと短くできますが実行速度では変わらないでしょう。ちなみにforループで書いて、ローカル変数の無駄をなくしたら次のようにできます。
void calcProcess(unsigned long now){
unsigned long cnt=0;
for(; now > 1; now = (now%2 ? now-1 : now/2), cnt+=1);
printf("%ld\n", cnt);
}
C++やC99以降のCならforループでcntを宣言できるのでもう1行短くなります。
問題には入力値は最大10,000,000とありましたが、この処理はほぼ対数時間で終わります。なので10,000,000程度なら気にしなくて大丈夫です。
この説明を書いていて気付いたのですがビット演算を使ってもうまくできると思います。
そちらの方が速いでしょうか？