Rekursiv oder iterativ?

Neue Aufgabe, neues Glück. Warum also nicht mit glücklichen, äh, fröhlichen Zahlen weitermachen. Es gibt dafür sogar eine passende Function Kata. Eine fröhliche Zahl ist laut Wikipedia: „eine natürliche Zahl, die als Ausgangswert für eine bestimmte Iterationsvorschrift nach endlich vielen Iterationsschritten zu dem Zahlenwert 1 führt.“

Bei jedem Iterationsschritt wird dabei die Summe aus dem Quadrat der einzelnen Ziffern berechnet. Dies wird dann so lange wiederholt bis entweder die 1 als Ergebnis herauskommt oder man sich im endlosen Zyklus von 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 befindet. In diesem Falle ist es eine nicht fröhliche, also traurige, Zahl.

Hier ein Rechenbeispiel für die fröhliche Zahl 7:

7 → 7² = 49 → 4² + 9² = 97 → 9² + 7² = 130 → 1² + 3² + 0² = 10 → 1² + 0² = 1

Bei einer solchen Problemstellung denkt man schnell an eine Rekursion. Damit sieht eine einfache Lösung für die fröhliche Zahlen zwischen 10 und 20 so aus:

using System;
using System.Linq;

class Program
{
  private static void Main()
  {
    foreach (var num in Enumerable.Range(10, 10).Where(IsHappy))
    {
      Console.WriteLine(num);
    }
  }

  private static bool IsHappy(int nr)
  {
    if (nr == 1) return true;
    if (nr == 4) return false;
    nr = nr.ToString().Select(x => x - '0').Sum(x => x * x);
    return IsHappy(nr);
  }
}

Diese Lösungsvariante prüft ob es die Zahl für den aktuellen Iterationsschritt eine 1 ist, in diesem Falle ist die Zahl fröhlich. Handelt es sich hingegen um eine 4, so ist es eine nicht fröhliche Zahl. Die Lösung geht davon aus, dass es reicht eine Zahl in der Kette für die nicht fröhlichen Zahlen zu prüfen. Ist die Zahl weder eine 1 noch eine 4, so wird die nächste Iteration berechnet und die Prüfung per Rekursion erneut durchgeführt. Die Berechnung macht sich zunutze, dass die einzelnen Stellen der Zahl über eine Zeichenkette leicht ermittelt werden können. Diese Zeichen können dann mithilfe von LINQ leicht verarbeitet werden.

Die Lösung ist kurz und knapp. Vielleicht ist die Performance aufgrund des Umwegs über die Zeichenkette nicht die beste, aber für die Prüfung der 10 Zahlen ist diese mehr als Ausreichend. Stört, die Rekursion ist dies auch kein Problem. Wir können diese schnell durch eine Iteration ersetzen. Der ReSharper kann dies auf Wunsch sogar automatisch. Hat er doch eine passende Refaktorisierung an Board. Hier die versprochene iterative Lösung:

using System;
using System.Linq;

class Program
{
  private static void Main()
  {
    foreach (var num in Enumerable.Range(10, 10).Where(IsHappy))
    {
      Console.WriteLine(num);
    }
  }

  private static bool IsHappy(int nr)
  {
    while (true)
    {
      if (nr == 1) return true;
      if (nr == 4) return false;
      nr = nr.ToString().Select(x => x - '0').Sum(x => x * x);
    }
  }
}

Und wie würde eine Lösung nach Flow Design aussehen? Der obige Code könnte durchaus auch eine Lösung nach Flow Design darstellen. Bei der Methode IsHappy() würde es sich dann um eine Operation handeln und die Main() wäre eine verkappte Integration. Verkappt deshalb, da eine reine Integration nach dem IOSP keine Logik enthalten darf. Dies könnte aber schnell behoben werden, indem die foreach-Schleife in eine zweite Operationsmethode verlagert wird, welche die einzige Aufgabe hat, Zahlen auf dem Bildschirm auszugeben.

Mir ist das an dieser Stelle dennoch nicht gut genug. Um eine bessere Lösung zu finden, sollten wir erst mal wieder die einzelnen Teilschritte finden:

• Zu prüfende Zahlen zwischen 10 und 20 generieren
• Iterationsschritt(e) berechnen
• Auf (nicht)fröhliche Zahl prüfen
• Ergebnis ausgeben

Hier das passende Flow Design für die Methode IsNumberHappy():

Und hier die Umsetzung als vollständiges Programm für die Zahlen von 10 bis 20:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
  private static void Main()
  {
    var numbersToCheck = CreateNumbersToCheck(10, 20);
    var happyNumbers = numbersToCheck.Where(IsNumberHappy);
    PrintHappyNumbers(happyNumbers);
  }

  private static IEnumerable<int> CreateNumbersToCheck(int from, int to)
  {
    return Enumerable.Range(from, to - from);
  }

  private static bool IsNumberHappy(int number)
  {
    var iterations = CalculateIterationsForNumber(number);
    return CheckForHappyness(iterations);
  }
  
  private static void PrintHappyNumbers(IEnumerable<int> happyNumbers)
  {
    foreach (var num in happyNumbers)
    {
      Console.WriteLine(num);
    }
  }
  
  private static IEnumerable<int> CalculateIterationsForNumber(int number)
  {
    while (true)
    {
      yield return number;
      var numberChars = number.ToString().ToCharArray();
      var numberDigits = numberChars.Select(x => x - '0');
      number = numberDigits.Sum(x => x * x);
    }
  }

  private static bool CheckForHappyness(IEnumerable<int> iterations)
  {
    foreach (var iteration in iterations)
    {
      if (iteration == 1) return true;
      if (iteration == 4) break;
    }
    return false;
  }
}

Dank dem Schlüsselwort yield kann das hier entworfene Flow Design leicht umgesetzt werden. Ich bin mit der Lösung nach Flow Design an dieser Stelle auch ganz zufrieden. Natürlich könnte man für eine noch bessere Lösung die Methode CalculateIterationsForNumber() aufteilen. Dies wäre für ein so kleines Beispiel dann aber vielleicht doch etwas zu viel. Weshalb ich am Ende bei der gezeigten Lösung bleiben möchte.

Ich hoffe, ich konnte mithilfe eines weiteren Beispiels Flow Design wieder ein Stückchen näher bringen. Für den ein oder anderen mag die gezeigte Lösung zwar overengineered sein, aber durch die Separierung sind die Aufgaben schön voneinander getrennt. Und das bildet doch eine gute Basis für das Thema Evolvierbarkeit.

Anmerkung: Bei diesem Text handelt es sich um einen überarbeiteten Repost eines alten Blog-Artikels aus 2015 von mir.