Image

The “Lost in Recursion” Recursion

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. gizmo

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. 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.

• Brent

“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.