Tree of SCIENCE!!! #4

Here's where things on the Tree of SCIENCE!!! start to get more interesting, and somewhat more obscure:

i-3f09ecf95ddcb93471385cfa05fafe68-sm_tree.jpg

Yes, that's a small wooden Christmas tree ornament hanging on our full-size Christmas tree. What's this have to do with SCIENCE!!!? Well, obviously, it represents recursion.

recursion, as you know Bob, is an extremely useful technique in computer programming, whereby you define a function in terms of itself. The classic example of this is the factorial function:

n! = 1*2*3*...*(n-1)*(n)

You can write a program to calculate the factorial of a number by defining a function f(n) that has two possible outputs:

  • If n=1, it returns f(1)=1.
  • If n>2, it returns f(n)=n*f(n-1).

If you spend a few minutes thinking about what this does for a specific number-- 17, say, because it's the mystical number-- you can convince yourself that it will, in fact, give you the factorial for any n.

Recursion lets you write extremely short programs to do infinitely complicated tasks, and as such is an invaluable tool for computer programming. And, of course, it's almost impossible to do science these days without computers.

Thus, recursion gets a place on the Tree of SCIENCE!!!

More like this

Time for another sort-of advanced basic. I used some recursive definitions in my explanation of natural numbers and integers. Recursion is a very fundamental concept, but one which many people have a very hard time wrapping their head around. So it's worth taking the time to look at it, and see…
What do you call a biologist who uses bioinformatics tools to do research, but doesn't program? You don't know? Neither does anyone else. The names we use People who practice biology are known by many names, so many, that the number of names almost reflects the diversity of biology itself.…
So in the last few posts, I've been building up the bits and pieces that turn lambda calculus into a useful system. We've got numbers, booleans, and choice operators. The only thing we're lacking is some kind of repetition or iteration. In lambda calculus, all iteration is done by recursion. In…
Yet another term that we frequently hear, but which is often not properly understood, is the concept of optimization. What is optimization? And how does it work? The idea of optimization is quite simple. You have some complex situation, where some variable of interest (called the target) is based…

uh...

pardon me, Professor, but shouldn't this: n! = 1*2*3*...*(n-1)*(n-2)

actually be this: n! = 1*2*3*...*(n-1)*(n) ?

(Annoying Copy Editor Girl can't shut up. Yes, I was THAT girl in university.)

pardon me, Professor, but shouldn't this: n! = 1*2*3*...*(n-1)*(n-2)

actually be this: n! = 1*2*3*...*(n-1)*(n) ?

That mistake might help explain why the author thinks it should take "a few minutes" of thought to realize that the recursive definition of n factorial yields n factorial.

It's worth noting that the factorial can be defined iteratively, that the recursion is in the definition, not the function, and that there's no recursion in placing a little replica of a tree on a tree. The very least this Christ-addled fool could have done is attached a yet-smaller replica of a tree onto the replica of a tree ...

By truth machine (not verified) on 18 Dec 2007 #permalink

pardon me, Professor, but shouldn't this: n! = 1*2*3*...*(n-1)*(n-2)

actually be this: n! = 1*2*3*...*(n-1)*(n) ?

Yeah, that's a typo. Fixed now.

The very least this Christ-addled fool could have done is attached a yet-smaller replica of a tree onto the replica of a tree ...

Welcome to Uncertain Principles! Enjoy your stay!

Honestly, some days, the Internet makes me despair...

P.S.

Recursion lets you write extremely short programs to do infinitely complicated tasks

I (literally) can't imagine what an "infinitely complicated task" is, but rest assured that if there are any such beasts, recursion doesn't let you program them. Recursion is useful for tasks, complicated or otherwise, in which a function can be defined in terms of itself. For instance, factorial(n) = n*factorial(n-1), or the height of a tree (data structure) is 1 + the max value of the heights of the subtrees of the root.

By truth machine (not verified) on 18 Dec 2007 #permalink

Honestly, some days, the Internet makes me despair...

Why does having your stupidity revealed make you despair? It is we who should despair.

By truth machine (not verified) on 18 Dec 2007 #permalink