En iyi algoritmayı (asimptotik olarak) aramak ve diğer ayrıntıları göz ardı etmek

Donanım yığınını kullanmadan özyineli algoritmalar uygulamak mümkündür. Yığın taşması olasılığı ciddi bir sorunsa, kendi yığınınızı uygulayabilir veya sadece özyinenin derinliğini sınırlandırabilirsiniz.

However, if the algorithm is dividing a set of data (of size n) recursively, then the number of recursions will be proportional to log n. This means that to exhaust a stack of size s you need data of size on the order of 2^s, which grows extremely quickly with s. People tend to not appreciate how quickly the exponential function is growing. My point is that with this type of algorithm (splitting a set of data in each recursive step) it is quite unlikely that the input data can be large enough to need so many recursions as to exhaust the stack.

EDIT: But then I'm not a professional programmer, so I'm lacking on the practical experience front.

İşte ilk gördüğüm çabuk bir şakadır:

f(x)
{
  for (;;)
  {
    if (x is trivial)
    {
      return;
    }
    x1 = one half of problem x
    x2 = other half of problem x
    if (x1 is the little half)
    {
      x = x2;
      f(x1);
    }
    else
    {
      x = x1;
      f(x2);
    }
  }
}

Bunun anlamı, her özyinelemeli çağrının problemin küçük bir yarısı olmasıdır - tipik olarak asıl sorunun büyüklüğünün yarısından daha azdır - ve problemin daha büyük yarısı iterasyon yoluyla yapılır. Sorun 2 ^ n boyutundaysa, yığın yalnızca n boyutunda olmalıdır, çok eşitsiz bölünmeler nedeniyle - n log n yerine n ^ 2'ye yakın bir zamana sahip olursanız bile.

"Gerçek maliyet", n log n zaman fakat yığın yığınları kullanan algoritmalara dayanıyorsa, n log n'de çalışan bir algoritmanın n log n'den daha fazla kullanma zamanına sahip olmadığına dikkat edin. bir yığın yığını, aslında, örneğin Bir Java tercümanı, programınızı kaçış özyinesine sahip olduğunuz izlenimi ile çökertir.