Tech Tip #72: Memoise expensive recursion

Naive recursion can repeat the same calculation millions of times.

The problem

A recursive function that calls itself on overlapping sub-problems recomputes the same answers again and again. The textbook example is Fibonacci; real code does it with tree walks, pricing rules and path searches.

The fix you can use today

  • Cache results of pure functions: functools.lru_cache in Python, a map elsewhere.
  • Or turn the recursion into a bottom-up loop.
  • Only memoise pure functions whose inputs repeat.

A study found that storing results of repeated calls can cut energy by up to 74%. GreenCode's energy rules for AI coding agents cover this too.

Tools that help

  • GreenCode Constitution skill (GreenCode researchers): open-source energy principles and a catalogue of 37 energy anti-patterns that an AI coding agent can follow to find and fix waste like this
  • green-languages (GreenCode researchers): a command-line tool that measures the energy of whole programs or marked sections of code, across languages

How GreenCode helps

GreenCode helps tackle this by refactoring flagged code one element at a time: it writes any missing tests and documentation first, and returns every change as a pull request for a person to approve. More on this.

Tags

#algorithms#caching#python

Sources

All GreenCode Tech Tips

  • Tip #72
  • For Developers
  • Category Code efficiency
  • Format short video
GreenCode

Want this checked on your own system? Talk to the GreenCode team.

Get in touch