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

[Lasse Reichstein Nielsen]

"Csaba Gabor" <da*****@gmail.com> writes:

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
--
Lasse Reichstein Nielsen - lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

[Dr John Stockton]

JRS: In article <8x**********@hotpop.com>, dated Fri, 14 Apr 2006
12:43:27 remote, seen in news:comp.lang.javascript, Lasse Reichstein
Nielsen <lr*@hotpop.com> posted :

"Csaba Gabor" <da*****@gmail.com> writes:

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.

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.

--
© John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 MIME. ©
Web <URL:http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links.
PAS EXE TXT ZIP via <URL:http://www.merlyn.demon.co.uk/programs/00index.htm>.
Do not Mail News to me. Before a reply, quote with ">" or "> " (SoRFC1036)

[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