Recursive function and enumerators

Question

4.00/5 (1 vote)

See more:

C#

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:

C#

void f() { g(3); }

C#

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

I'd like to change this to

C#

void f1() { foreach (var x in .... ) }

This is what I tried

C#

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 26-Jun-12 7:33am

Julio Kuplinsky

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

TRK3 · Answer 1 · 2012-06-26T08:28:00

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.

Clifford Nelson · Answer 2 · 2012-06-26T08:39:00

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?

Posted 26-Jun-12 8:39am

Clifford Nelson

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