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]

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

 

[Lasse Reichstein Nielsen]

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.

No problems spring to mind, that you haven't already mentioned.
My first guess was to check Wikipedia, but you're way ahead of them,
so you might consider updating their entry with your examples:
<URL:http://en.wikipedia.org/wiki/Overlapping_subproblem>

Hmm, on the other hand, there are lots of examples of algorithms
using dynamic programming. Those should be overlapping problems:
<URL:http://en.wikipedia.org/wiki/Dynamic_programming>

Good luck. Crosspost and Followup-To: sci.math, which I think is
more appropriate.
/L

 

[Dr John Stockton]

JRS: In article <[email protected]>, dated Fri, 14 Apr 2006
12:43:27 remote, seen in Lasse Reichstein

No problems spring to mind, that you haven't already mentioned.

The OP posted to too many newsgroups for me to see the article.

JAD9514.PAS, via sig line 3, may provide an example for those who can
read a 58-line Pascal program :-



{ Determine the number of ways of giving change for PTot pence,
using the coins in Pence. }

{$DEFINE CACHE}

....

Note : Without CACHE, time for Total=500 is intolerable ;
With CACHE, imperceptible ;




Whenever the number of possible sub-problems permits, sub-problem
results should be cached in a suitable structure. For numeric problems,
the elements of the initial structure can be non-existent, undefined, or
NaN.

Ackermann's Function is another example.