再帰的なC++関数

Question

次のように再帰関数を作成しようとしています。

関数はカウンターkをとり、限りカウンタがゼロより大きいことを、私は最後に、私はこのようなもので終わるように再帰的にそれを呼び出すしたいと思います：

result = 2(2(2n+1)+1)+1 

最後n（k = 0の場合）はゼロでなければならない。

int pass(int k, int n) 
{ 
    if(k==0) 
    { 
     n = 0; 
    } 
    else 
    { 
     k--; 
     return pass(k, 2*n+1); 
    } 
} 

誰かが私にどのようにヒントを与えることができますか？

Answer 1

変更

n = 0; 

結果を返します。

残りのコードは正常です。

Answer 2

現在、すべてのコントロールパスで明示的に値を返さないため、コードの動作は未定義です。私は三項条件演算子を使用しました。ここ

int pass(int k, int n) 
{ 
    return k ? 2 * pass(k - 1, n) + 1 : 1; 
} 

：

あなたのコードはまで簡素化することができます。 kがゼロでない場合は2 * pass(k - 1, n) + 1が返され、それ以外の場合は1が返されます。

この場合、intがオーバーフローしないように注意してください。 intの最大サイズは32767と小さくてもかまいません。代わりにlongタイプを使用することを検討してください。

また、通常、再帰はO（n）型の問題を解決する良い方法ではありません。関数呼び出しのスタック制限を超えているため、実行時にエラーが発生する可能性があります。代わりにループに折り畳むことを検討してください。

return n; 

へ