一般的な再帰インタビュー挑戦

おい、皆さん!ようこそコードレビューには、一連のコーディングの課題と仕事関連のコンテンツを毎週公開されます.我々は、ホリデーシーズンのための短い中断を取ったが、我々は戻って、2020年に我々が得たすべてを表示する準備が整いました.CoderByteの我々のチームは我々の日仕事から離れて余分の時間を与えられて離れてハッキングしていました、そして、我々には2020年に計画される若干の大きなものがあります.

ニュースレター📫

最初に、私たちの新しいニュースレターに言及して興奮しています!私たちは、何か大きなものを解放するたびに、小さな、機能を明らかに断片化を送信するつもりですので、私たちのコミュニティは、私たちが何か新しいものを壊す知って最初です.Give us your email hereと我々は“最初に知っている”リストに追加します.2020年への歓声!🎉

問題点:

四半期、ダイム、ニッケル、およびペニーの無限の量を与え、コインでnセントを表す方法の数を返す関数を記述します.

いくつかのヒントが再発になる

再帰は時間が圧倒的に得ることができます.再帰的な問題へのアプローチを考え出すとき、本当にリラックスするのに役立つ何かが、定義によって、再帰的な解決はより小さな副問題への解決で構成されていることを思い出しています.
古典的な“nフィボナッチ数”チャレンジを計算します.場合は、この1つを聞いていない-フィボナッチシリーズは、各番号は、0と1から始まる2つの前のものの合計である数のシーケンスです.我々はボトムアップのアプローチを取ることができます、そこで、我々は単純なケースのために問題を解決して、そこでそれを構築して、解決します.この問題の最も単純なケースは、シリーズの定義に従って0を返すFibonacciシリーズの第0番数を得ることです.のは、1つは、定義ごとに1を返す1番号を取得するために構築しましょう.Fibonacciシリーズの2番目の数を計算するために、我々は0と1を追加し、我々は別の1を得る.3番目の数を計算するには、1と1を追加し、2を得る.そして、0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...に続きます.
これは以下のように要約できます.fibonacci(0)は常に1になります.その後、fibonacci(1)は2つの先行番号の合計である.
この問題では、fibonacci(n)が1であり、fibonacci(n-1)が0のときには常に1を返します.
これは以下のようになります.

function fibonacci(n) {
  if (n === 0) return 0
  if (n === 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

ビッグオー

しばしば再帰的な解決のBIG - Oを見つけるために、それは再帰木としてコード経路を描くのを助けます.上の例では

ルールはこれです:各ノードが木に持っている枝の量は力のベースです、そして、木のレベルは指数です.この例では、それぞれの関数呼び出しが2つの関数呼び出しに分割されるので、BIG - Oはfibonacci(n-2)です.また、ツリーのレベル数はnに相当する.
すべての楽しみを持って、次のソリューションとブランドの新しいチャレンジを参照してください!