Web Development

Memoize recursive functions to conserve resources

Memoization is an effective technique for conserving system resources, especially in languages that don't do tail call optimization.

Memoization is a form of caching that is used to reduce duplication of effort by your program. In short, it is a means of caching results so that when generating large data sets the same results do not need to be recalculated as part of an otherwise elegant algorithm.

The most common use of memoization is in recursion. Most programmers are aware of recursion; some even understand and use it. The majority of modern functional programming languages provide tail call optimization, but those languages that do not (usually object oriented or merely procedural) include some of the most widely used programming languages. Tail call optimization is typically considered in terms of an interpreter or compiler that optimizes a recursive function so that it will not perform the same operations over and over again. In languages that lack tail call optimization, a similar effect is achieved through memoization.

An example of an algorithm that could benefit greatly from tail call optimization or memoization is the recursive definition of a Fibonacci number:

F(0) = 0

F(1) = 1

F(n > 1) = F(n-1) + F(n-2)

This is a prime example of the importance of optimization in programming. The simplistic recursive source code for this in Ruby would look something like this:

def fib(n)

return n if [0,1].include? n

fib(n-1) + fib(n-2)

end

Unfortunately, the most widely used production version of Ruby today, Ruby 1.8.7, does not support tail call optimization (look for it in Ruby 1.9+). If n = 4 in the above code, it ends up being calculated like this:

fib(4)

(4 - 1)

+ (4 - 2)

(((4 - 1) - 1) + ((4 - 1) - 2))

+ (((4 - 2) - 1) + ((4 - 2) - 2))

((((4 - 1) - 1) - 1) + (((4 - 1) - 1) - 2)) + (3 - 2)

+ (2 - 1) + (2 - 2)

(((3 - 1) - 1) + ((3 - 1) - 2)) + 1

+ 1 + 0

((2 - 1) + (2 - 2) + 1

+ 1

(1 + 0) + 1

+ 1

1 + 1

+ 1

2

+ 1

3

That's a lot of effort just to get the number three. The problem is that, until the numbers start getting down to 0 or 1, every operation requires two sub-operations. With a high enough Fibonacci number to start the process, the number of operations required gets absolutely insane. Using the Ruby REPL, you can see that the fourth Fibonacci number requires nine calls to the fib() method, and the fifth Fibonacci number requires 15 calls:

> irb

irb(main):001:0> $opcount = 0

=> 0

irb(main):002:0> def fib(n)

irb(main):003:1> $opcount += 1

irb(main):004:1> return n if [0,1].include? n

irb(main):005:1> fib(n-1) + fib(n-2)

irb(main):006:1> end

=> nil

irb(main):007:0> fib 4

=> 3

irb(main):008:0> $opcount

=> 9

irb(main):009:0> $opcount = 0

=> 0

irb(main):010:0> fib 5

=> 5

irb(main):011:0> $opcount

=> 15

By the time you get to fib 20, you have 21,891 calls to fib(). fib 30 took more than 10 seconds to complete in a test run, and 2,692,537 calls to fib().

Memoization greatly reduces the number of such operations that must be performed, by only requiring each Fibonacci number to be calculated once. For the simple version, start by creating an array to hold already calculated numbers. For each calculation, store the result in that array. For each time a recursive function would normally calculate one of those numbers, check to see if the number is stored in your array; if so, use that, and if not, calculate and store it. As a jump-start to the array, set the first two elements to 0 and 1, respectively.

In Ruby, a Fibonacci number generator might be modified to look like this:

$fibno = [0,1]

def fib(n)

return n if $fibno.include? n

($fibno[n-1] ||= fib(n-1)) + ($fibno[n-2] ||= fib(n-2))

end

By caching values as you go so that fewer recursive calls are needed, you can get the result of fib 30 pretty much instantaneously. The total number of recursive calls to fib() is reduced from 2,692,537 to a mere 29. In fact, the number of calls to fib() increases linearly, so that the number of calls is always equal to the ordinal value of the Fibonacci number you want minus one. That is, fib 50 makes 49 calls to fib(), and fib 100 makes 99 calls to fib().

That assumes you reset $fibno every time. You can leave it alone, and reduce the number of calls to fib() even more on subsequent calls. For instance, try fib 100 with $fibno = [0,1], and 99 calls to fib() will be made. Try fib 40 without resetting $fibno, though, and only one call to fib() will be made, because $fibno already contains the appropriate value.

You can also use a somewhat simpler approach to caching than the above example. Instead of the number of calls to fib() only increasing by one for each increase in the ordinal Fibonacci value, it increases by two, resulting in 59 operations instead of 29 for fib 30:

$fibno = [0,1]

def fib(n)

$fibno[n] ||= fib(n-1) + fib(n-2)

end

Similar caching mechanisms can be used to achieve similar effects in other languages that do not optimize tail calls, such as C, Java, and Perl. In fact, in Perl this caching idiom has a special name: the Orcish Maneuver. The name comes from the or-equals operator, ||=, which can be pronounced "or cache" in cases such as memoization. Say "or cache" very quickly, and you get the name of something that bears the stamp of a favorite fantasy monster. Perhaps this is how an Orc would optimize a recursive function, after all.

In Perl, the term Orcish Maneuver is typically applied to sorting functions rather than recursive series generation functions as in the case of memoizing a Fibonacci number generator. The canonical Perl example of the Orcish Maneuver looks something like this:

my @words = (

'four',

'one',

'three',

'two'

);

my %numbers = (

'one' => 1,

'two' => 2,

'three' => 3,

'four' => 4,

);

my @numerically_sorted_words;

sub str2n {

my $key = shift;

$numbers{$key};

}

{ my %cache;

@numerically_sorted_words = sort {

($cache{$a} ||= str2n($a)) <=> ($cache{$b} ||= str2n($b));

} @words;

}

foreach (@numerically_sorted_words) { print "$_\n"; }

A probably more useful application of Perl's Orcish Maneuver would be for month names, but this example at least shows how the maneuver is used.

About

Chad Perrin is an IT consultant, developer, and freelance professional writer. He holds both Microsoft and CompTIA certifications and is a graduate of two IT industry trade schools.

25 comments
VosaBz
VosaBz

Thank you for defense of me. Apotheon sems rather outraged. I asked my question only for pure linguistic interest. Every word in every langauage has its history and its origin. Why it is necessary to omit an "r" from "memorize" to create a technical term "memoize"? Is there no adequate English word that a new one shoud be introduced? When and where this word "memoize" was used first? Have a nice day, all of you. Vosabz

valduboisvert
valduboisvert

PERl has some already made modules that can help with memoization, Memoize.pm being a well known one. *edit* btw, I like your articles. Thanks.

VosaBz
VosaBz

Since English is not my mother tongue I was surprised with your invention of the word "memoization" beacause I suppose you mean "memorization", i.e. remembering. Vosa

Mark Miller
Mark Miller

I recognize the point of your article was to talk about some computational techniques for optimization, just generally, but I thought it'd be constructive to point out that sometimes a computation can be optimized even further by using mathematics. I've been studying the textbook SICP (Structure and Interpretation of Computer Programs) off and on, and it talks about a variety of ways to optimize Fibonacci, a couple of which are iterative, rather than recursive (though it uses tail recursion optimization for iteration in Scheme). The first linear optimization it suggests is in the transformation: T: a

Tony Hopkinson
Tony Hopkinson

is not to, there again, I mainly work with procedural or OO, both of which are notoriously crap at it, especially on this sort of function which ranges to infinity. I could see myself doing something similar even in loop though where it would have a similar benefit. Choice would then be added complexity of the code (not that much) versus how often I expect to be recalcing the same values.

Sterling chip Camden
Sterling chip Camden

In your Fibonacci example, only the second recursive call would benefit from tail-call optimization if the language provided it. The first call is not in a tail position. So even if the language provided TCO, memoization still dramatically improves the performance of the higher number cases for this algorithm.

apotheon
apotheon

Nobody is outraged here, unless it is: * you outraged at my abuse of the word "memorize" -- which, as Sterling already pointed out, is ridiculous, since "memoize" is not even derived from "memorize" * deepsand outraged at me for asking a simple question, because he apparently likes reading ill intent into innocent questions As for why you asked your question -- you did not in fact ask a question. You simply stated that I was inventing words, and cast aspersions on the decision to do so, despite the fact I did not invent a word at all in this case. I can only assume your hypercorrectivity came about through a lazy unwillingness to check on whether the term predates this article. You have, however, finally asked an actual question that is not obviously rhetorical, so I will answer it: > When and where this word "memoize" was used first? It was first used (as far as I'm aware) by Donald Michie, in his paper "Memo Functions and Machine Learning", which was published in a 1968 issue of Nature.

Sterling chip Camden
Sterling chip Camden

... we invent new terms every day. We need to, because we continuously create specialized concepts that need labels. "Memoize" is not made from the word "memorize" -- it's made from the related word, "memo". When you memoize something, you create a memo of your past result so you don't have to recompute it.

apotheon
apotheon

Thanks for bringing it up. I intentionally left out the standard Perl module and Ruby gem for memoization because I did not want to write an article about those libraries so much as about how memoization worked. In retrospect, I suppose a brief mention of each would have been helpful anyway. I'm glad you brought up the Perl module, though. . . . and thanks for the compliment, re: my articles.

apotheon
apotheon

Shouldn't you at least check to see whether Google or Wikipedia knows a word before you start assuming people invented it on the spot?

apotheon
apotheon

SICP is definitely a challenging book for people who do not have a very strong educational background in math -- including me. I started working my way through it last year (or was it the year before?), and ended up having to put it aside because I was spending too much time on it and not enough on other things. Of course, the point of developing iterative optimizations for intuitively recursive operations in SICP is to eventually implement Scheme such that when using the language you can use tail recursion efficiently, without having to resort to iteration in your Scheme code.

apotheon
apotheon

. . . but this wasn't about tail call optimization, so I didn't bother using an example with tail calls.

VosaBz
VosaBz

Thank you, now I understand. VosaBz

VosaBz
VosaBz

Sorry, but I supposed the nost relevant resources are Webster or Oxford dictionaries. Google provides everything anybody writes and Wikipedia likewise.

apotheon
apotheon

First, you quoted me: > "Tail call optimization ... optimizes a recursive function so that it will not perform the same operations over and over again." Then, you paraphrased me as if you were contradicting me: > TCO is about saving stack space by converting tail call recursion into a looping construct. You explained it as some kind of disputation by saying: > It has nothing to do with optimizing which operations are performed. Nobody said anything about optimizing which operations are performed. The comment was about how many operations are performed. Perhaps you are not aware of this fact, but compiling a recursive operation to a looping operation replaces a recursive call stack that builds until the last needed recursion is tucked into the stack with an operation that simply executes then replaces itself with the next loop. Your statement that both tail call optimization and memoization can be used on the same recursive function, but that does not in any way change the fact that in the absence of tail call optimization the use of memoization becomes much more important -- and, in fact, tail call optimization often eliminates much of the need for memoization. You might notice my snarky rephrasing of the title of your off-site response, as the title of this comment. That's because you apparently skimmed what the article said, then assumed a lot was said that in fact wasn't, and didn't understand the basic meaning of the words that were actually written. I recommend you look to your understanding of what people say before accusing them of failing to understand what they themselves are saying.

apotheon
apotheon

Since I'm only on the hook for two articles a month in the Programming and Development column, I probably won't end up writing that follow-up -- though I encourage others to do so if they like. I would rather tackle subjects that interest me more than that, I'm afraid -- especially given that the generalized nature of those libraries tends to lead to less of a performance boost than memoizing by hand, and the process of memoizing in those languages is so simple in the general case that there really is not much code saved by using them, so I don't use them much.

apotheon
apotheon

I didn't load the question. If it's "loaded" in your view, you're the one who loaded it by reading into it rather than merely reading it.

deepsand
deepsand

You gave him a choice of two answers, answers which failed to encompass the whole. Furthermore, such question was unnecessary, as said member's question was already answered.

apotheon
apotheon

I was not being aggressive in the comment to which you replied. I asked a question. I do not see how asking a simple question is "aggressive".

deepsand
deepsand

The member in question clearly stated that English is not his mother tongue; he also stated that he thought that you meant "memorize." Your hostility is misplaced.

apotheon
apotheon

Are you trying to tell me I'm wrong because Webster isn't a computer science dictionary, or are you trying to explain why you made the mistake of claiming the term "memoize" was "invented" for this article and apologize for the error?

Sterling chip Camden
Sterling chip Camden

... often remain uncovered by Webster or Oxford. Google only provides a sample of global usage, and favors the most popular usages. Technical jargon, by definition, has little overlap with popular usage.

Editor's Picks