Click here to Skip to main content
14,329,993 members
Rate this:
Please Sign up or sign in to vote.
See more:
Suppose that I have a recursive function that generates a sequence, and I want to return the items one at a time. I DON'T want to create the sequence in memory b/c 1) the individual items can be large 2) the sequence can be long 3) depending on the use of the sequence, I might have to look at the first few elements only.

Here is a toy example:

void f() { g(3); } 


int g(int k} {
  if(k < 10) {
    k = g(k + 1);
    Console.WriteLine(k);
  }
  return k + 1;
}


I'd like to change this to
void f1() { foreach (var x in .... ) }


This is what I tried
IEnumerable<int> g2(int k, out int h) {

  h = k + 1; // set h before exiting

  if(k < 10) {
    g2(k + 1, out k);
    yield return k;
  }
}


Doesn't work: you can't have out params with iterators. I tried other things (looks like you can't use the return value of g2 to set k because IEnumerable\<int\> is not and int), but I don't want to tax your patience. Any ideas? thnx.
Posted
Rate this:
Please Sign up or sign in to vote.

Solution 1

There are ways to do that, none of which appear to be good:

http://stackoverflow.com/questions/2055927/ienumerable-and-recursion-using-yield-return[^]

http://arnonaxelrod.wordpress.com/2010/08/19/traversing-binary-tree-using-an-iterator/[^]

To summarize:

You either do all the recursion each time you want to yield the next value (very expensive).

Or you run the recursion in another thread and have the enumerator communicate with that thread.



I would suggest a different approach:

Rather that trying to wrap your recursive function in a enumerator, pass a function to your recursive function, something like this:

int MyRecursiveFunction(int k, bool MyItemHandler(int k)) 
{
    if (k == 0) {

       MyItemHandler(k);
       return k;

    } else {

       if (MyItemHandler(k))
          return k;
       else 
          return MyRecursiveFunction(k - 1, MyItemHandler);
    }
}


The idea is to call MyItemHandler on each item that the recursion generates (on the way down).

If MyItemHandler returns true you abort the recursion, and otherwise return false to continue the recursion.

Not sure my example code will quite do what you want, or that the syntax is correct, but it's just to illustrate the idea. The actual implementation I leave to you.
   
Rate this:
Please Sign up or sign in to vote.

Solution 2

Why not have the iterator return a class that contatains both the return value (an int) and the have the h value as the other item?
   
Comments
Julio Kuplinsky 26-Jun-12 14:51pm
   
For the same reason: an IEnumerable<x> is not an X.
Julio Kuplinsky 26-Jun-12 14:52pm
   
Argh.. this thing ignores angle brackets: for the same reason: an IEnumerable\<x\> is not an X

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100