Posted by Jasen Betts on 04/15/06 02:25

On 2006-04-14, Csaba Gabor <danswer@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

[Back to original message]