ruby 20 lines · 5 steps

Memoizing Fibonacci with a Hash default block

A Hash with a self-populating default block turns Fibonacci into a lazily-built, cached lookup table.

Explained by highlit
Intermediate memoization recursion hash-default lazy-evaluation
1module Fibonacci
2 CACHE = Hash.new do |cache, n|
3 cache[n] = cache[n - 1] + cache[n - 2]
4 end
5 
6 CACHE[0] = 0
7 CACHE[1] = 1
8 
9 module_function
10 
11 def [](n)
12 raise ArgumentError, "n must be non-negative" if n.negative?
13 
14 CACHE[n]
15 end
16 
17 def sequence(count)
18 Array.new(count) { |i| self[i] }
19 end
20end
01 / 01
STEP 01

Walkthrough

Space play ←→ step click any line
Three takeaways
  1. 1A Hash default block can compute and store missing values, giving you memoization for free.
  2. 2Seeding base cases up front lets a recursive default block terminate cleanly.
  3. 3Wrapping the cache behind a method lets you validate input without losing the caching benefit.

Related explainers

ruby 
class ToastBroadcaster
  include ActionView::RecordIdentifier
 
  def self.broadcast_to(user, message:, type: :notice)

How Turbo Stream toasts broadcast in Rails

turbo-streams service-object real-time
Intermediate 6 steps
ruby 
class TemplateInterpolator
  PLACEHOLDER = /\{\{\s*([\w.]+)\s*\}\}/
 
  def initialize(strict: false)

Interpolating templates with dotted keys in Ruby

regex string-interpolation hash-traversal
Intermediate 6 steps
java 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

Building a trie for autocomplete in Java

trie prefix-tree recursion
Intermediate 8 steps
ruby 
class KeyTransformer
  def self.camelize(data)
    new.camelize(data)
  end

Recursively camelizing nested Ruby data

recursion data-transformation pattern-matching
Intermediate 7 steps
ruby 
module Paginatable
  extend ActiveSupport::Concern
 
  private

A reusable pagination concern in Rails

pagination concerns http-headers
Intermediate 8 steps
ruby 
class Api::MessagesController < ApiController
  before_action :authenticate_api_key!
 
  rate_limit to: 100,

Layered API rate limiting in Rails

rate-limiting api-authentication throttling
Intermediate 9 steps

Share this explainer

Here's the card — post it anywhere.

Memoizing Fibonacci with a Hash default block — share card
Made with highlit — turn any snippet into a walkthrough like this in about a minute.
Explain your code