How to Get Rid of Recursion, or How My Code Ended Up in Google
summary
A comparison of several techniques for eliminating or optimizing recursion in code, with measured performance numbers for each approach: tail recursion, DeepRecursiveFunction, using a queue, a TreeIterator, and Sequence.yield. During the study the presenter found a major performance bug in the standard ViewGroup.descendant function, explains how it was discovered, and describes contributing a fix to Google that sped the function up by hundreds of times and was accepted.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 3:30Last year's results
- 4:55What recursion is and why avoid it
- 7:11Tail recursion limits
- 11:56Recursion problems in JVM
- 13:00Hierarchy traversal without recursion
- 15:29Lazy iterator for hierarchies
- 19:05Universal recursion removal
- 28:25Google problem and solution
- 37:28Why viance is slow
- 40:21When to use recursion
- 41:26Q&A