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!)
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.
“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.
Paul teaches math and mathematical art at Saint Ann's School. He lives in Brooklyn with his wife, Teresa, their daughter Nora, and their dog, Buster Bluth. He loves to juggle and play music.
Paul Salomon
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!)
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?
Pingback: Exponents and the Scale of the Universe – a 21st Century math lesson | Lost In Recursion
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.
Pingback: Carnival of Mathematics 86 | The Math Less Traveled