0Pricing
Competitive Programming Academy · レッスン

再帰的に考える: Base と Recurse

問題をより小さな同型の問題に分解します

「再帰的に考える: Base と Recurse」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

再帰とは

再帰とは、問題をより小さな部分に対して自分自身を呼び出して解き、その部分が直接答えられるほど小さくなるまで続ける関数です。🌀

小さい問題への呼び出しを信頼する

重要な考え方は信じて任せることです。小さい入力に対する再帰呼び出しはすでに正しく動くと仮定し、その結果をもとに答えを組み立てます。

すべての再帰にはベースケースが必要

ベースケースとは、再帰せずに答えを出す最小の入力です。これがないと、関数は永遠に自分自身を呼び出し続け、クラッシュします。

再帰ケース

再帰ケースでは、問題を小さくして、より小さい形に対して自分自身を呼び出します。各呼び出しは、ベースケースに近づかなければなりません。

最初の例としての階乗

ここで階乗は、0の場合のベースケースと、nから1を引いた値に対する再帰呼び出しという2つの部分を示しています。

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)

コールスタックの仕組み

各呼び出しは、内側の呼び出しが戻るまでコールスタック上で待機します。最も深い呼び出しが最初に完了し、その後、結果が上へ順に戻っていきます。

再帰の深さに注意

Pythonでは、デフォルトで再帰の深さが約1000に制限されています。競技プログラミングで深い再帰を使う場合は、実行時エラーを避けるためにsys.setrecursionlimitを使う必要があります。

import sys
sys.setrecursionlimit(300000)

呼び出しごとに必ず前進する

正しい再帰では、入力を必ずベースケースに近づけるように小さくします。もし同じ大きさに戻ることがあれば、永遠にループします。⚠️

リストを再帰的に合計する

この再帰的な合計では、最初の要素を取り除き、残りのリストを呼び出し先が加算するものとして処理します。

def total(a):
    if not a:
        return 0
    return a[0] + total(a[1:])

再帰木で分岐を把握する

関数が複数回呼び出されると、処理は再帰木を形成します。その大きさから、処理全体のコストが分かります。

同じ処理の繰り返しは遅くなる

素朴なフィボナッチ計算では同じ値を何度も再計算するため、指数時間になります。計算結果をメモ化すれば、すぐに解決できます。

クイックチェック

再帰関数にベースケースがないと、どうなりますか？

まとめ：2つの部分で1つの考え方

再帰には、処理を止めるベースケースと、入力を小さくする再帰ケースが必要だと学びました。小さな入力に対する呼び出しを信頼すれば、残りの処理も自然に進みます。🎯

よくある質問

「再帰的に考える: Base と Recurse」レッスンは無料ですか？

はい。「再帰的に考える: Base と Recurse」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「再帰的に考える: Base と Recurse」で何を学びますか？

問題をより小さな同型の問題に分解します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「再帰的に考える: Base と Recurse」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 再帰的に考える: Base と Recurse
  2. すべての部分集合を生成する
  3. 順列と N-Queens の考え方
  4. 制限時間を守るために枝刈りする
← Competitive Programming Academyに戻る