インタラクティブPythonラボ

Fibonacci (Recursive)

プレイグラウンドはロード時に自動実行されます。コードを実行をクリックして自分のPythonをトレースしましょう — 各ステップがライブアニメーション。

説明·行ごと

リプレイ·ステップごと

チャレンジ·ガイド付きプロンプト

XP·...

データフローパイプライン

advanced トラック

Bubble Sort

Two Sum

Valid Parentheses

Merge Sort

Quick Sort

Heap Sort

Breadth-First Search

Depth-First Search

Binary Tree Traversal

Fibonacci (Recursive)

説明

Line 1

fib(8): naive recursion. Will make ~2^8 = 256 function calls.

なぜこのアプローチ？

Naive fib has no memory of previous results. fib(8) calls fib(7) and fib(6). fib(7) calls fib(6) again. fib(6) is computed many times — this exponential blowup makes it impractical for n > 40.

Structured Explanation

Overview

再帰的フィボナッチ: f(n)=f(n-1)+f(n-2)。単純だが指数時間でメモ化が必要。

Analogy

家系図のように — 各人は両親から情報を得る。

Step-by-step

基底ケース: f(0)=0, f(1)=1
それ以外: return f(n-1) + f(n-2)
これはO(2^n) — 非常に遅い
@lru_cacheでO(n)に改善

Visual

fib(4) ├─fib(3) fib(2) │ ├─fib(2) fib(1) ├─fib(1) fib(0) │ └─fib(1) fib(0)

Common mistakes

メモ化なしで大きいnに使う
基底ケースが0や負で正しく処理されない

Practice questions

@functools.lru_cacheでfib()をデコレート
メモ化なし/あり/反復の時間を比較

Time

O(2^n)なし、O(n)メモ化あり

Space

O(n)

複雑度

時間

O(2ⁿ) naive / O(n) memoized

空間

O(n)

複雑度概要

O(1)

O(log n)

O(n)時間空間

O(n log n)

O(n²)

n = 8範囲 1-20

N = 8 のとき

複雑度	操作
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

チャレンジ

再帰的フィボナッチを実装しましょう。fib(10)とfib(35)を確認し、時間の違いに注目。

ヒント

dictキャッシュでメモ化を追加します。呼び出しツリーが2^nからnに劇的に削減。

コードスタジオ

Fibonacci (Recursive)

Monaco準備完了

Python準備完了

lesson.pyline 1

Loading editor...

出力コンソール

0 lines

まだ出力がありません...

タイムライン

データ構造

コールスタック (プリミティブ & 参照)

nint

スタック値

8

call count (approx)obj

スタック値

~256

実世界の応用例

1

Teaching how easily systems crash

2

Why caching architectures exist

3

Stress-testing recursion constraints

Comments

Loading comments...