Image

The “Lost in Recursion” Recursion

20120312-113512.jpg

About these ads

9 responses to “The “Lost in Recursion” Recursion

  1. Me likey. With 20 seconds of experience looking at this, my first question is whether or not you’ll always eventually end up with a number.

    • That is to say, will you ever get lost in recursion?

      I gave this problem to Anna Weltman about a year ago. She came back after working a night on one of the harder exercises and said, “OK, I’m lost in recursion.” Hence the name! (Thanks, Anna!)

  2. Am I correct in saying that f(n,a,b)=a OP b, where OP is defined by n as addition,multiplication,exponentiation,tetration,ETC?

  3. Pingback: Exponents and the Scale of the Universe – a 21st Century math lesson | Lost In Recursion

  4. It looks similar to the Ackermann function, but not quite. For one thing, it takes three arguments.

    n and b never increase, and sufficiently small integer values have base cases, so f(a, n, b) will terminate provided n≥0, b≥1, neZ, beZ.

    • Firstly, you’re very right about termination and the allowable input values. Secondly, I had never heard of the Ackermann function, and I definitely need to keep reading about it, but they are definitely connected. The wikipedia article says there are many variations as well, so perhaps this is one of them. It also says the original function did have 3 inputs, so perhaps its exactly this.

      I was certain that other people had had this same idea. I call that a Coen-Ventorism. It’s named after Coen and Ventor, two hypothetical mathematicians who simultaneously coinvented the concept.

      In this case, it’s the notation that’s the breakthrough and makes the problem accessible to all.

      Thanks so much for sharing.

      • Just did some reading on Wikipedia. This is indeed the original three-argument Ackermann function! How exciting!

        I wonder if I should stop calling it the “Lost in Recursion” recursion. Well it is how I got the name, anyway.

    • “n and b never increase” — actually that’s not true. b can certainly increase in rule (iii) (when b is equal to the result of a recursive triangle). What we can say, however, is that either n decreases, or n stays the same and b decreases.

  5. Pingback: Carnival of Mathematics 86 | The Math Less Traveled

What do you think?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s