Ja, so eine Software gibt es. Findest du vieles, wenn du die Google-Suche mit „Stammbaum Software“ oder „Family Tree Software“ konfrontierst. Es gibt auch einige Web-Tools dazu.
Wegen der Empfehlung müsste ich meinen Schwiegeropa fragen, der hat von seiner Familie so etwas mal erstellt, er hat auf Grund von Aufzeichnungen die Linie relativ weit zurückverfolgen können.
Allerdings wirst du das Problem haben, dass du bei genügend Verwandten, das niemals auf eine A4-Seite bekommst. Ich glaube mein Schwiegeropa, der das bei sich aufgehängt hat, hat so die Maße von 6x4 A4-Seiten (weiß es grad nicht, vllt. hat ers auch auf A3 gedruckt).
“Anfrage stellen”: gemeinsame Urururururururururgroßmutter? usw.)
Hm… müsste gehen, ansonsten einfach die Stammbaumlinien zurückverfolgen. Oder du überträgst das in PROLOG 
Theoretisch könntest du sowas auch mit einem UML-Diagramm machen. 