想象一下，我需要维护数百万个产品。如何递归地导航所有相关产品并识别已经访问过的产品？
不必使用递归。显式的
Stack或
Queue可以用于导航部分。为了收集结果，可以使用
HashSet而不是
List。它将有两个目的-允许您跳过已经访问的元素，并消除最后
Distinct的需要。
以下是基于
Queue的示例实现：
public List<Product> GetTopRelatedProducts(int N)
{
var relatedSet = new HashSet<Product>();
var relatedListQueue = new Queue<List<Product>>();
if (RelatedProducts != null && RelatedProducts.Count > 0)
relatedListQueue.Enqueue(RelatedProducts);
while (relatedListQueue.Count > 0)
{
var relatedList = relatedListQueue.Dequeue();
foreach (var product in relatedList)
{
if (product != this && relatedSet.Add(product) && product.RelatedProducts != null && product.RelatedProducts.Count > 0)
relatedListQueue.Enqueue(product.RelatedProducts);
}
}
return relatedSet.OrderByDescending(x => x.Rating).Take(N).ToList();
}
更新：为了完整性，这里列出了相关集合收集部分的其他可能实现：
使用显式的Stack：
public List<Product> GetTopRelatedProducts(int N)
{
if (RelatedProducts == null || RelatedProducts.Count == 0)
return new List<Product>();
var relatedSet = new HashSet<Product>();
var pendingStack = new Stack<List<Product>.Enumerator>();
var relatedList = RelatedProducts.GetEnumerator();
while (true)
{
while (relatedList.MoveNext())
{
var product = relatedList.Current;
if (product != this && relatedSet.Add(product) && product.RelatedProducts != null && product.RelatedProducts.Count > 0)
{
pendingStack.Push(relatedList);
relatedList = product.RelatedProducts.GetEnumerator();
}
}
if (pendingStack.Count == 0) break;
relatedList = pendingStack.Pop();
}
return relatedSet.OrderByDescending(x => x.Rating).Take(N).ToList();
}
虽然比显式
Queue实现稍微冗长，但该方法的空间要求较少-
O(height)其中
height是最大深度。
迭代实现的好处是它们当然可以处理比递归解决方案更大的深度，后者可能导致
StackOverflowExpection。但是，如果不希望深度太大并且更喜欢递归，则以下是一些递归实现（它们只需要访问
relatedSet和
this）：
使用经典的私有递归方法：
public List<Product> GetTopRelatedProducts(int N)
{
var relatedSet = new HashSet<Product>();
GetRelatedProducts(this, relatedSet);
return relatedSet.OrderByDescending(x => x.Rating).Take(N).ToList();
}
private void GetRelatedProducts(Product product, HashSet<Product> relatedSet)
{
if (product.RelatedProducts == null) return;
foreach (var item in product.RelatedProducts)
if (item != this && relatedSet.Add(item))
GetRelatedProducts(item, relatedSet);
}
使用递归lambda：
public List<Product> GetTopRelatedProductsD(int N)
{
var relatedSet = new HashSet<Product>();
Action<Product> GetRelatedProducts = null;
GetRelatedProducts = product =>
{
if (product.RelatedProducts == null) return;
foreach (var item in product.RelatedProducts)
if (item != this && relatedSet.Add(item))
GetRelatedProducts(item);
};
GetRelatedProducts(this);
return relatedSet.OrderByDescending(x => x.Rating).Take(N).ToList();
}
最后但并非最不重要的，使用最新的C# 7.0新增功能 - 递归本地函数：
public List<Product> GetTopRelatedProducts(int N)
{
var relatedSet = new HashSet<Product>();
GetRelatedProducts(this);
return relatedSet.OrderByDescending(x => x.Rating).Take(N).ToList();
void GetRelatedProducts(Product product)
{
if (product.RelatedProducts == null) return;
foreach (var item in product.RelatedProducts)
if (item != this && relatedSet.Add(item))
GetRelatedProducts(item);
}
}
所有这些方法（在我看来）都最优地处理了收集部分。当然，前N部分不是最优的 - O(N*log(N))，可以像@Amit Kumar的答案中提到的那样进行优化，但这需要实现一个缺失的标准数据结构，这超出了SO答案的范围。
Product实例吗？ - Ivan Stoev