# Weekend thought provoker - nonclean overlapping recursion

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
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

## Re: Weekend thought provoker - nonclean overlapping recursion

Csaba  Gabor wrote:

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

## Re: Weekend thought provoker - nonclean overlapping recursion

Ackerman overlaps? it seemed to me more like it blows out.

I'm sure I've seen a heuristic solution to that one.

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.

there are non-recurssive solutions for this one too...

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