?

Log in

No account? Create an account

t3knomanser's Fustian Deposits

Wagging the Tail: Recursion and You

How Random Babbling Becomes Corporate Policy

run the fuck away

Mad science gone horribly, horribly wrong(or right).

Wagging the Tail: Recursion and You

Previous Entry Share Next Entry
run the fuck away
I want to make coffee. To do that, I need to put six scoops of coffee into our french press. If I were writing this repeated effort as a program, I could do it in two different ways: iteratively or recursively.

The iterative version is the approach most of us would take to this task. Something like:
scoops = 0; while scoops < 6 scoop_coffee, scoops = scoops + 1;.
In plain English, scoop and keep scooping until I've done it six times. Iterative logic is built around repeating a task.

That's great for certain problems. But there's another trick that programmers have in their arsenal, something that we all intuitively look to for solving complex problems. That other tool is recursion.

Iteration is repeating the same simple task over and over again to complete your goal. Recursion is taking a complex task and breaking it up into sub-tasks until you hit some simple case. Then you do that. Going back to the coffee example, I can break the task up into sub-tasks. To get six scoops, I need to scoop five scoops and one more. To scoop five scoops, I need to scoop four scoops, and one more. And so on.

In pseudocode, it would look something like this:
scoop(1) :- get_a_scoop_of_coffee.
scoop(n) :- scoop(n-1),get_a_scoop_of_coffee.


If I only need one scoop, get it. If I need more than one scoop (n), get n-1 scoops, and get one scoop of coffee.

For a simple task, like getting coffee, this is counterintuitive. It's not how we think about simple tasks. But for complex tasks, recursion is often far easier to use. If I want to sort a long list, for example, it's easier to implement it recursively than iteratively. A recursive sorting algorithm would say, "Hey, sorting a list is hard work. So I'll make it easier. I'll sort the first half of the list, I'll sort the second half of the list, and then I'll merge the results." Well, how do you sort the first half of the list? Well, you can break that in half and sort the two halves and merge the results. And you can keep breaking things into halves until you get a list with two elements. Hey! Two elements are really easy to sort (this is known as the merge sort; another good problem to solve recursively is the Towers of Hanoi puzzle- that one you can play along at home).

Programmers have a love/hate relationship with recursion. It's a very powerful technique, and recursive code is often very beautiful, compact, and readable code. But it's hard code to really understand. It's hard to adjust to thinking recursively. Recursion is one of those things that makes or breaks programmers, and the sort of thing that drives CS majors to flee to the Business division.

But recursion has a very dark side. In most languages, in most implementations, it's very expensive. Every time you call a procedure, a bunch of memory gets allocated on what's called "the stack". The bigger and more complex the procedure, the more memory you need on the stack. And if you keep calling the same procedure over and over again, the stack keeps getting taller and taller.

If we're just interested in theory, that's not really important. Elegant, compact code is better than practical code. But, sadly, we exist in the real world, not the theoretical one. So what are we to do?

Well, the first thing I must do is admit I lied to you. Remember my "get coffee" pseudocode? It wasn't pseudocode. It wasn't pseudocode at all. It's actually a code snipped of Prolog- a programming language heavily used in AI research. Prolog relies very heavily on recursion- there's not really any other way to easily do repeated tasks. Another language, LISP, requires that nearly everything is done with recursion. But, if recursion is expensive, doesn't that mean that these languages must suck?

It turns out, if you're a very clever language designer, you can actually solve this problem using a technique known as "tail recursion". Let's go back to my recursive coffee maker.
scoop(1) :- get_a_scoop_of_coffee.
scoop(n) :- scoop(n-1),get_a_scoop_of_coffee.

See that scoop(n-1) bit? That's the recursive call. To get n scoops of coffee, first get n-1 scoops and one more. This program is bad, and will have all of those memory problems I was warning you about.
This version, on the other hand, doesn't:
scoop(1) :- get_a_scoop_of_coffee.
scoop(n) :- get_a_scoop_of_coffee,scoop(n-1).


What's the trick? Just putting the recursive call at the end makes all the difference in the world. Tail recursion tells the program that get_a_scoop_of_coffee doesn't need to know the results of scoop(n-1). Which means I don't need to keep building stuff up on the stack- so when Prolog executes this code, while I wrote it recursively, it executes iteratively.

This is a big deal for languages like Prolog and LISP. They need recursion to do anything. So they need a way to make recursion cheap, and tail recursion does that job.

Now, here's the really interesting thing: Prolog and LISP are both heavily used in AI research. They're not the only languages, but they're big ones, and they depend heavily on recursion. What does that tell you about the nature of intelligence, or at least how we understand intelligence?

Okay, you ask, why did Remy just abuse my brain with all this recursion crap? Because, I've been learning Prolog with an eye towards learning a bit about AI design, and I learn best by teaching. And that means I intend to take you with me.

I'm going to start a round of Prolog tutorials to explain the basics of programming. I'll start from the ground up, which means you don't need to know anything about programming to get into them. All you need to do is download a Prolog interpreter, and for my examples, I recommend SWI Prolog. It comes with an integrated text editor that makes it very easy to try out programs and query them.
  • Recursion is one of those things that makes or breaks programmers, and the sort of thing that drives CS majors to flee to the Business division.

    Someone seems to have forgotten what his wife majored in at university...
    • You didn't flee CompSci for Business. You majored in CompSci and also majored in Business.
  • Happy memories. I was surprised at how shockingly easy it was to implement tail-call optimization. It was so easy that the forth derivative I've been implementing for work had to have it.
Powered by LiveJournal.com