累乗（再帰）
累乗（再帰）
このレッスンで分かること
- 引数が複数あっても、再帰の考え方は同じ
- 素朴な再帰版の
powerはexp回再帰呼び出しを行うので、計算量はO(exp)です累乗はbase ^ exp(base の exp 乗) のことです
累乗 とは
pow(base, exp)を再帰で実装し、引数 2 つでの再帰呼び出しと指数のデクリメントを学ぶ。
累乗 は base ^ exp (base の exp 乗) のことです。2 ^ 3 = 8, 5 ^ 0 = 1, 3 ^ 4 = 81 というあれです。本レッスンでは pow(base, exp) を 再帰 で実装します。前の 2 レッスン (factorial / fib) と違うのは、引数が 2 つあること。再帰呼び出しで base はそのまま、exp だけ 1 ずつ減らしていく、という点に注目してください。
引数が複数あっても、再帰の考え方は同じ。
基底ケースと自己呼び出しの 2 つを書くだけだ。
数学的な定義
累乗は次のように定義できます。
pow(base, 0) = 1(どんな数も 0 乗は 1)pow(base, exp) = base * pow(base, exp - 1)(exp >= 1)
これをそのままコードに落とすと、Python ではこうなります。
Python
def power(base, exp):
if exp == 0:
return 1
return base * power(base, exp - 1)基底ケース は exp == 0、再帰ケース は base * power(base, exp - 1) です。exp を 1 ずつ減らしていけば、いつか 0 に到達して 1 を返します。
再帰の流れを Mermaid で見る
power(2, 4) がどう展開されるかを Mermaid で描いてみましょう。
図のポイント (テキスト併記)
power(2, 0)が基底ケースに到達して1を返し、そこから順に2を掛けながら戻っていきます
power(2, 0) が 基底ケース に到達して 1 を返し、そこから順に 2 を掛けながら戻っていきます。最終的に 16 が返ってくる、というわけです。
JavaScript / Java での書き方
JavaScript
function power(base, exp) {
if (exp === 0) return 1;
return base * power(base, exp - 1);
}Java
public class Solution {
public static long power(int base, int exp) {
if (exp == 0) return 1L;
return base * power(base, exp - 1);
}
}計算量と高速化
素朴な再帰版の power は exp 回再帰呼び出しを行うので、計算量は O(exp) です。実は 分割統治 を使うと O(log exp) まで高速化できます (高速指数法)。
pow(base, exp) = pow(base, exp / 2) ^ 2の発想を使えば、再帰の深さは半分ずつになる。
この 高速指数法 は中級向けの応用なので、まずは素朴な O(exp) の実装をきっちり書けるようになりましょう。
よくある間違い
if exp == 1: return baseを基底ケースにすると、pow(base, 0)が0を返してしまう。正しくはexp == 0を基底ケースにする。pow(base, exp - 1) * baseとbase * pow(base, exp - 1)のどちらでも結果は同じだが、後者の方が数式に近くて読みやすい。expの代わりにbaseを減らしてしまう (たとえばpower(base - 1, exp)) と、無限ループしないが結果が壊れる。再帰呼び出しで何を変えるかを明確にする。
やってみよう
下の coding 課題で、power(base, exp) を再帰で実装してください。テストでは base が 0 から 5、exp が 0 から 10 の範囲で正しい結果が返るかを確認します。
0 の 0 乗をどう扱うかは数学的に議論があるが、本レッスンではpower(0, 0) = 1の規約を採用する。これはプログラミングの世界では一般的な約束だ。
Go 版での書き方
Go
func power(base int, exp int) int {
if exp == 0 {
return 1
}
return base * power(base, exp-1)
}Go でも、書き方は他の言語とほぼ同じ。基底ケースを if exp == 0 で書いて、それ以外は base * power(base, exp-1) を返すだけです。再帰 の構造は言語をまたいでこのくらい似ています。
補足: 数学の漸化式と再帰の関係
累乗 の漸化式 pow(b, e) = b * pow(b, e - 1) をそのままコードにしたのが、本レッスンの再帰版実装です。漸化式 (recurrence relation) と 再帰関数 (recursive function) は、ほぼ同じ形をしています。数学の漸化式 を見たら、再帰 で書ける可能性がある、と発想するクセをつけると、アルゴリズム設計の幅が広がります。
第 6 章 (動的計画法) で扱う フィボナッチ 階段の登り方 コイン両替 などは、すべて 漸化式 を出発点にして再帰または DP で解く問題です。本章の factorial fib power は、その入門編に当たります。素朴な再帰でしっかり書けるようになったら、次は メモ化 や DP に進む準備が整います。
よくある質問
Q. 再帰とループはどっちを使うべき？
A. ツリー構造や分割統治（merge sort, BST 走査）は再帰が自然で読みやすくなります。シンプルな反復処理はループが速くスタックも消費しません。再帰深さが配列長に比例する場合、スタックオーバーフローのリスクがあるため気をつけてください。
Q. 再帰のベースケースを忘れるとどうなる？
A. 無限再帰になりスタックオーバーフローします。最初の 1 行目に if (base) return; を書く習慣を付けると安全です。Python は sys.setrecursionlimit で上限を変えられますが、根本的にループに書き換える方が安定します。
Q. 再帰を高速化する方法は？
A. 同じ引数で再計算しているなら memoize（メモ化）で結果をキャッシュします。Python は functools.lru_cache、Java/JS は HashMap で実装します。フィボナッチを memo 付きにすると指数 O(2ⁿ) から線形 O(n) に劇的に高速化します。
次のレッスン
次は 配列の合計（再帰） で、配列を先頭 1 要素と残りに分解して再帰的に合計を求める書き方を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- 累乗 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. 累乗 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 関数
power(base, exp)を実装し、整数値を返す - for / while を使わず、必ず再帰で実装する
- 基底ケースは exp == 0 のとき 1 を返す
入出力例
test-cases.txt
power(2, 3) → 8
power(5, 0) → 1
power(0, 5) → 0
power(3, 4) → 81
power(2, 10) → 1024
power(1, 7) → 1