Weekend thought provoker - nonclean overlapping recursion

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • Csaba  Gabor

    #1

    Weekend thought provoker - nonclean overlapping recursion

    I suppose spring fever has hit at alt.math.underg rad 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

    #2
    Re: Weekend thought provoker - nonclean overlapping recursion

    Csaba Gabor wrote:[color=blue]
    > I'm looking for problems that have double (or more) recursion[/color]
    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
    Carl Vondrick is a YM Associate Professor of Computer Science at Columbia University, researching computer vision, machine learning, and AI applications.

    Comment

    • Jasen Betts

      #3
      Re: Weekend thought provoker - nonclean overlapping recursion

      On 2006-04-14, Csaba Gabor <danswer@gmail. com> wrote:
      [color=blue]
      > I suppose spring fever has hit at alt.math.underg rad 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[/color]

      Ackerman overlaps? it seemed to me more like it blows out.
      [color=blue]
      > 2. Tower of Hanoi[/color]

      I'm sure I've seen a heuristic solution to that one.
      [color=blue]
      > 3. Determining the nth number in the Fibonacci or Lucas series[/color]

      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.
      [color=blue]
      > 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])[/color]

      there are non-recurssive solutions for this one too...
      [color=blue]
      > I'm especially happy for those problems that have a physical analogue.[/color]

      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

      Comment

      Working...