递归函数和枚举器 [英] Recursive function and enumerators

问题描述

假设我有一个生成序列的递归函数，并且我想一次返回一个项目.我不想在内存b/c中创建序列1)单个项目可能很大2)序列可能很长3)根据序列的用途，我可能不得不看一下前几个元素仅.

这是一个玩具示例:

  void  f(){g( 3 ); } 

  int  g( int  k} {
  如果(k <   10 ){
    k = g(k +  1 );
    Console.WriteLine(k);
  }
  返回 k +  1 ;
} 

我想将其更改为

 无效 f1(){ foreach ( in  ....)} 

这就是我尝试过的

 IEnumerable< int> g2( int  k， out   int  h ){

  h = k +  1 ; // 在退出前将h设置

  如果(k <   10 ){
    g2(k +  1 ， out  k);
    收益 收益 k;
  }
} 

无效:您无法使用迭代器来实现参数.我尝试了其他方法(由于IEnumerable \< int \>不是int和int，因此您无法使用g2的返回值来设置k)，但是我不想增加您的耐心.有任何想法吗? thnx.

解决方案

有多种方法可以实现，但似乎没有一个很好:

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

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

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.

解决方案

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.

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?

这篇关于递归函数和枚举器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！