Browse by Tags

Tagged Content List
  • Blog Post: Recursion, Part Six: Making CPS Work

    JScript doesn't support CPS natively but we can write another dispatch engine that makes it work. There's only ever one active continuation, so lets have a new rule: JScript CPS functions are allowed to return, but the last thing that they do must be to tell our dispatch engine what the continuation...
  • Blog Post: Recursion, Part Five: More on CPS

    Suppose we wanted to write this by-now-familiar little function in continuation passing style: function treeDepth(curtree) { if (curtree == null) return 0; else { var leftDepth = treeDepth(curtree.left); var rightDepth = treeDepth(curtree.right); return 1 + Math.max(leftDepth, rightDepth); } } ...
  • Blog Post: Recursion, Part Four: Continuation Passing Style

    We're getting hung up on the stack management aspects of recursive programming. Why do we need a stack at all? What purpose does it serve? If you're like most developers, you probably learned about subroutines and functions at an early age. The idea is pretty straightforward. You stop what you're...
  • Blog Post: Recursion, Part Three: Building a Dispatch Engine

    There's a particular technique that I like to use to solve problems -- it doesn't always work, but when it does, it can produce programs of surprising elegance and power. The technique is this: if you have a specific problem to solve, solve a more general problem, and then your problem is just a special...
  • Blog Post: Recursion, Part Two: Unrolling a Recursive Function With an Explicit Stack

    That recursive solution is pretty cool, to be sure. But there is one big problem with it. Consider this Jscript program that puts a few more nodes into our tree from last time: function tree(value, left, right) { this.value = value; this.left = left; this.right = right; } for (var i = 1 ; i < 1500...
  • Blog Post: Recursion, Part One: Recursive Data Structures and Functions

    The first thing to wrap your head around is recursively defined data structures. Let's start with something simple. Think about the abstract idea of “list”. Most people think of a “list” as an ordered collection of “items”, one after the other, with a beginning and an end. That’s a very non-recursive...
  • Blog Post: Recursion, Part Zero

    I’ve mentioned recursive programming techniques several times over the years in this blog ( Topological Sort , How Not To Teach Recursion , Fibonacci Challenge , Recursion and Dynamic Programming , Sometimes Breadth Is Better Than Depth , and probably a few others). A lot of developers, particularly...
  • Blog Post: Recursion and Dynamic Programming

    Back in May we were discussing the merits and drawbacks of recursive programming techniques -- that is, writing functions which break down problems into sub-problems, and then call themselves. The drawback of such an approach is that in some cases, you end up doing way more work than necessary...
Page 1 of 1 (8 items)