Weekend thought provoker - nonclean overlapping recursion

[Csaba Gabor]

I suppose spring fever has hit at alt.math.undergrad since I didn't get
any rise from
them when I posted this a week ago, so I am reposting this to some of
my favorite
programming groups:

I'm looking for problems that have double (or more) recursion, where
the split is not
clean (ie. where there may be overlap). Let's call this overlapped
recursion, where the
same subproblem may have to be solved multiple times.

By way of illustration.
Single recursion:
factorial

Clean double recursion:
merge sort
depth first searches (DFS), and other binary tree
Overlapped recursion (what I'd like more examples of):
1. Ackermann's function and relatives
2. Tower of Hanoi
3. Determining the nth number in the Fibonacci or Lucas series
4. Counting the number of ways to change 1 dollar (ie. number of
distinct ways to sum
numbers (repetitions allowed) from a list L to arrive at N. In the
example N=100 and L=[1,
5, 10, 25, 50])

I'm especially happy for those problems that have a physical analogue.

Thanks,
Csaba Gabor from Vienna

[Carl Vondrick]

Csaba Gabor wrote:

I'm looking for problems that have double (or more) recursion

Are you looking for problems to solve?

Here's an interesting one that I have been playing around with recently (not
sure if this is what you wanted or not):

x_n = k + y_n-1 + abs(x_n-1), x_0 = 1
y_n = x_n-1, y_0 = 2

If you play with your seeds and k, you get some interesting stuff.

Carl

--
Carl Vondrick
Web-Engineer
www.carlsoft.net

[Jasen Betts]

On 2006-04-14, Csaba Gabor <da*****@gmail.com> wrote:

I suppose spring fever has hit at alt.math.undergrad since I didn't get
any rise from
them when I posted this a week ago, so I am reposting this to some of
my favorite
programming groups:

I'm looking for problems that have double (or more) recursion, where
the split is not
clean (ie. where there may be overlap). Let's call this overlapped
recursion, where the
same subproblem may have to be solved multiple times.

By way of illustration.
Single recursion:
factorial

Clean double recursion:
merge sort
depth first searches (DFS), and other binary tree
Overlapped recursion (what I'd like more examples of):
1. Ackermann's function and relatives
Ackerman overlaps? it seemed to me more like it blows out.
2. Tower of Hanoi
I'm sure I've seen a heuristic solution to that one.
3. Determining the nth number in the Fibonacci or Lucas series
Possible with single recursion:

F(n)= g(0,1,n)

g(a,b,n)= a where n=0
g( b, a+b , n-1 ) otherwise

And that's end-recursion which is just iteration in drag.
4. Counting the number of ways to change 1 dollar (ie. number of
distinct ways to sum
numbers (repetitions allowed) from a list L to arrive at N. In the
example N=100 and L=[1,
5, 10, 25, 50])
there are non-recurssive solutions for this one too...
I'm especially happy for those problems that have a physical analogue.

the class of problems solvable using overlapped recursion far exceeds the
class that must be solved in that way.

you may want to look in comp.lang.ml

Standard ML handles overlapped recursion in a sensible way and so
algorithms with the form you're looking for should be popular there.

Bye.
Jasen