Posted by Csaba Gabor on 04/14/06 06:43

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

[Back to original message]