Sachverhalt:
A.
X._ zwang A._ am 6. Oktober 2011 zwischen 21.00 Uhr und 22.15 Uhr, nachdem er ihr ein zirka 12 cm langes Messer an die Kehle gehalten und ihr damit eine oberflächliche Schnittwunde zugefügt hatte, zur Vornahme sowie Duldung verschiedener sexueller Handlungen, unter anderem des Geschlechtsverkehrs.
Ferner hielt sich X._ trotz gültiger Einreisesperre zirka von März 2009 bis am 24. November 2011 widerrechtlich in der Schweiz auf, wobei er während zirka eines Jahres auch arbeitete.
B.
Das Bezirksgericht Affoltern verurteilte X._ am 24. November 2014 wegen qualifizierter Vergewaltigung, mehrfacher qualifizierter sexueller Nötigung sowie Widerhandlung gegen das Ausländergesetz zu einer Freiheitsstrafe von neun Jahren und ordnete die Verwahrung an. Ferner entschied es über die Zivilforderungen von A._.
Gegen dieses Urteil erhoben X._, letztlich beschränkt auf die Strafzumessung und die Anordnung der Verwahrung, sowie die Staatsanwaltschaft IV des Kantons Zürich, beschränkt auf die Strafzumessung, Berufung. A._ führte Anschlussberufung, die einzig die Höhe der Genugtuung umfasste.
C.
Das Obergericht des Kantons Zürich stellte am 18. Oktober 2016 fest, dass das Urteil des Bezirksgerichts bezüglich der Dispositivziffern 1 (Schuldpunkt), 5 und 6 (Einziehungen), 7-12 (Kosten- und Entschädigungsdispositiv) sowie 14 (Schadenersatz) in Rechtskraft erwachsen ist. Es bestrafte X._ mit einer Freiheitsstrafe von 81⁄2 Jahren (Dispositivziffer 1) und sah von der Anordnung einer Verwahrung sowie einer therapeutischen Massnahme ab (Dispositivziffer 3). Ferner verpflichtete es X._, A._ eine zu verzinsende Genugtuung von Fr. 12'000.-- zu bezahlen (Dispositivziffer 4).
D.
Die Oberstaatsanwaltschaft des Kantons Zürich beantragt mit Beschwerde in Strafsachen, die Dispositivziffern 1 und 3 des obergerichtlichen Urteils seien aufzuheben und X._ sei mit einer Freiheitsstrafe von 111⁄2 Jahren zu bestrafen sowie zu verwahren. Eventualiter seien die genannten Urteilsdispositivziffern aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.
E.
Der Instruktionsrichter der Strafrechtlichen Abteilung bewilligte X._ auf dessen Gesuch vom 29. März 2017 hin mit Verfügung vom 9. August 2017 die unentgeltliche Rechtspflege sowie Verbeiständung für das bundesgerichtliche Verfahren und gab ihm Rechtsanwalt Thomas Schütz als Rechtsbeistand bei.
F.
Während das Obergericht auf eine Stellungnahme verzichtet, lässt sich X._ vernehmen und beantragt, die Beschwerde sei vollumfänglich abzuweisen, eventualiter sei Dispositivziffer 3 aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen.

Erwägungen:
1.
1.1. Die Beschwerdeführerin wendet sich gegen die Strafzumessung. Sie rügt, die Vorinstanz verletze Art. 47 sowie 50 StGB und überschreite ihr Ermessen, indem sie bezüglich der Sexualdelikte von einem objektiven Tatverschulden im unteren Bereich ausgehe. Sie argumentiert, ein objektives Verschulden in der Mitte des unteren Strafdrittels lasse sich nicht rechtsgenügend damit begründen, dass wesentlich grausamere Vorgehensweisen denkbar seien, da dies stets der Fall sei. Von entscheidender Bedeutung erscheine vorliegend allerdings nicht die Grausamkeit des Vorgehens des Beschwerdegegners, sondern vielmehr die Tatsache, dass er eine gefährliche Waffe verwendet habe und wie er diese gegenüber seinem Opfer eingesetzt habe. Diesbezüglich berücksichtige die Vorinstanz nicht, dass sich das Opfer in Lebensgefahr befunden habe, als der Beschwerdegegner ihm ein rund 12 cm langes Messer an die Kehle gesetzt sowie eine Schnittwunde zugefügt habe. Es sei daher von einem mittleren objektiven Tatverschulden auszugehen.
1.2. Die Vorinstanz gibt zunächst die Grundsätze der Strafzumessung wieder und setzt für das schwerste Delikt, die qualifizierte Vergewaltigung, die Einsatzstrafe auf rund fünf Jahre fest, wobei sie von einem objektiven Tatverschulden im unteren Bereich ausgeht und die subjektive Tatschwere als neutral wertet. In der Folge würdigt sie die Tatkomponenten für die mehrfache qualifizierte sexuelle Nötigung, wobei sie ebenfalls von einem Tatverschulden im unteren Bereich innerhalb des qualifizierten Tatbestands ausgeht, und erhöht die Einsatzstrafe um rund drei Jahre. Nach Würdigung der objektiven und subjektiven Tatkomponenten hinsichtlich der Widerhandlung gegen das Ausländergesetz bewertet sie das Verschulden des Beschwerdegegners als knapp noch leicht, weshalb sie die Einsatzstrafe leicht erhöht. Abschliessend würdigt sie die Täterkomponenten. Während sie die Einsatzstrafe aufgrund der Vorstrafen auf 91⁄2 Jahre erhöht, reduziert sie diese wegen des Geständnisses um ein Jahr. Insgesamt erachtet die Vorinstanz in Würdigung aller relevanten Strafzumessungsgründe eine Freiheitsstrafe von 81⁄2 Jahren den Taten, dem Verschulden und den persönlichen Verhältnissen des Beschwerdegegners als angemessen (Urteil S. 9 ff.).
1.3. Das Bundesgericht hat die Grundsätze der Strafzumessung nach <ref-law> wiederholt dargelegt (<ref-ruling> E. 5.4 ff. S. 59 ff. mit Hinweisen). Darauf kann verwiesen werden. Es liegt im Ermessen des Sachgerichts, in welchem Umfang es die verschiedenen Strafzumessungsfaktoren berücksichtigt. Das Bundesgericht greift auf Beschwerde hin nur in die Strafzumessung ein, wenn das Sachgericht den gesetzlichen Strafrahmen über- oder unterschritten hat, wenn es von rechtlich nicht massgebenden Kriterien ausgegangen ist oder wesentliche Gesichtspunkte ausser Acht gelassen beziehungsweise in Überschreitung oder Missbrauch seines Ermessens falsch gewichtet hat (<ref-ruling> E. 5.6 S. 61 mit Hinweis).
Nach <ref-law> hat das Gericht die für die Zumessung der Strafe erheblichen Umstände und deren Gewichtung festzuhalten. Es muss die Überlegungen, die es bei der Bemessung der Strafe vorgenommen hat, in den Grundzügen wiedergeben, so dass die Strafzumessung nachvollziehbar ist (<ref-ruling> E. 2.1 S. 20 mit Hinweisen).
1.4. Die Kritik der Beschwerdeführerin an der vorinstanzlichen Strafzumessung ist unbegründet.
Die Vorinstanz berücksichtigt bei ihrer Beurteilung des objektiven Tatverschuldens bei der qualifizierten Vergewaltigung, dass sich der Beschwerdegegner mit seinen Handlungen in egoistischer sowie erniedrigender Weise über das sexuelle Selbstbestimmungsrecht des Opfers hinweggesetzt und das ihm entgegengebrachte Vertrauen schamlos ausgenutzt habe. Weiter erwägt sie, zwar habe er sein Glied schon nach kurzer Zeit wieder aus der Vagina des Opfers herausgezogen, jedoch habe er ihm in der Folge in das Gesicht und den Mund onaniert, was zu einer weiteren Erniedrigung des Opfers geführt habe. Die Tatfolgen für das Opfer seien gravierend. Zu Beginn des Geschehens habe der Beschwerdegegner dem Opfer ein zirka 12 cm langes Messer an die Kehle gesetzt und ihm damit eine oberflächliche Schnittwunde zugefügt. In der hinsichtlich der Vergewaltigung zu beurteilenden zweiten Phase des Geschehens habe der Beschwerdegegner erneut ein Messer hervorgenommen, um seinen Forderungen Nachdruck zu verleihen. Dadurch sei das Opfer in grosse Angst geraten. Der Beschwerdegegner habe es mit seinem Vorgehen gefügig gemacht, das Messer jedoch auch wieder weggesteckt. Damit bewege sich das objektive Tatverschulden innerhalb des qualifizierten Tatbestands im unteren Bereich, da doch wesentlich grausamere Vorgehensweisen denkbar seien (Urteil S. 10 f.).
Hinsichtlich des objektiven Tatverschuldens bei der mehrfachen qualifizierten sexuellen Nötigung wiegt nach Ansicht der Vorinstanz nicht mehr leicht, dass der Beschwerdegegner das Opfer unter Bedrohung mit einem Messer mehrfach zu den sexuellen Handlungen nötigte. Es sei nicht nur zu Berührungen an den Brüsten, am Po sowie an der Vagina gekommen, sondern der Beschwerdegegner sei mit dem Finger mehrfach in die Vagina des Opfers eingedrungen und habe von diesem verlangt, dass es seinen Penis frottiere sowie ihn oral befriedige. Auch hier habe er sich in egoistischer und erniedrigender Weise über das sexuelle Selbstbestimmungsrecht des Opfers hinweggesetzt und dessen Vertrauen schamlos ausgenützt. Zudem hätten sich die Handlungen über einen längeren Zeitraum von über einer Stunde erstreckt. Aufgrund des Einsatzes des Messers sei auch hier das Qualifikationsmerkmal gegeben. Innerhalb des qualifizierten Tatbestands bewege sich das Verschulden am unteren Rand der Skala (Urteil S. 12).
Daraus ergibt sich, dass die Vorinstanz entgegen dem Einwand der Beschwerdeführerin den Einsatz des Messers berücksichtigt. Dies einerseits indem sie beziehungsweise die erste Instanz den Beschwerdegegner der qualifizierten Vergewaltigung gemäss <ref-law> und der (mehrfachen) qualifizierten sexuellen Nötigung gemäss <ref-law> durch Verwendung eines gefährlichen Gegenstandes schuldig spricht. Andererseits stellt sie bei der Strafzumessung in Rechnung, in welchem Ausmass die qualifizierenden Tatmodalitäten gegeben sind und gewichtet das konkrete Ausmass des verschuldeten Erfolgs. Dabei berücksichtigt sie, dass der Beschwerdegegner dem Opfer in einer ersten Phase (sexuelle Nötigung) das Messer an die Kehle hielt und ihm dabei eine oberflächliche Schnittwunde zufügte. Ebenso würdigt sie, dass er in einer zweiten Phase (Vergewaltigung) erneut ein Messer hervor nahm, um seinen Forderungen Nachdruck zu verleihen. Entgegen dem Einwand der Beschwerdeführerin berücksichtigt die Vorinstanz damit, wie der Beschwerdegegner die Messer gegenüber seinem Opfer einsetzte. Dass sie dabei die Vorgehensweise des Beschwerdegegners beziehungsweise deren Folgen nicht rechtlich würdigt und ausdrücklich festhält, er habe das Opfer dadurch in (abstrakte) Lebensgefahr gebracht, führt nicht dazu, dass sie mit der Einordnung des objektiven Tatverschuldens im unteren Bereich der Skala ihr Ermessen überschreitet. Ohne die Handlungsweise des Beschwerdegegners zu bagatellisieren, ist nicht zu beanstanden, dass die Vorinstanz erwägt, es seien wesentlich grausamere Vorgehensweisen denkbar. In diesem Zusammenhang scheint die Beschwerdeführerin zu übersehen, dass die Verwendung eines gefährlichen Gegenstands ein Anwendungsfall des grausamen Vorgehens im Sinne von Art. 189 Abs. 3 und <ref-law> ist. Es ist daher nicht zu bemängeln, dass die Vorinstanz das Vorgehen des Beschwerdegegners auf dessen Grausamkeit hin untersucht. Soweit die Vorinstanz das objektive Tatverschulden hinsichtlich der Sexualdelikte in Würdigung der objektiven Umstände, insbesondere der Tatsache, dass der Beschwerdegegner dem Opfer ein Messer an die Kehle hielt und es bedrohte, im unteren Bereich des qualifizierten Tatbestands festsetzt, überschreitet oder missbraucht sie ihr Ermessen nicht.
2.
2.1. Die Beschwerdeführerin kritisiert, dass die Vorinstanz keine Verwahrung anordnet. Die Voraussetzungen für eine Verwahrung gemäss Art. 64 Abs. 1 (lit. a) StGB seien vorliegend erfüllt. Beim Beschwerdegegner liege keine psychische Störung vor, er habe ein Anlassdelikt begangen und gemäss Gutachten sei ernsthaft zu erwarten, dass er weitere auch schwerwiegende Gewaltstraftaten begehen werde. Zudem sei auch das Erfordernis der Verhältnismässigkeit erfüllt. <ref-law> habe nicht zur Folge, dass ein im Strafregister entferntes Urteil bei der Frage des Bestehens einer Rückfallgefahr gezwungenermassen ausgeblendet werden müsse. Das urteilende Gericht habe bei den von ihm zu treffenden Entscheidungen alle dem Sachverständigen zustehenden Informationen zu berücksichtigen. Dementsprechend handle es sich nicht um negative Rechtsfolgen, die mit dem Einbezug des Urteils des Jugendgerichts durch den Sachverständigen in seinem Gutachten und mit der Berücksichtigung der Erkenntnisse des Sachverständigen durch das Gericht dem Beschwerdegegner entgegengehalten würden. Auch seien die Verwertungseinschränkungen der jugendstrafrechtlichen Registereinträge von Situationen im Erwachsenenstrafrecht gesondert zu betrachten. Die für die Einträge im Erwachsenenstrafrecht entwickelten Regeln könnten nicht uneingeschränkt auf jugendstrafrechtliche Verurteilungen angewendet werden, da im Jugendstrafrecht ein Registereintrag bereits nach erheblich kürzerer Zeit nach der Tat gelöscht werde und das Verhalten von Jugendlichen hinsichtlich der psychiatrischen Beurteilung von hervorragender (recte: herausragender) Bedeutung sei. Schliesslich verletze die Vorinstanz <ref-law>, indem sie die Einschätzung der Rückfallgefahr ohne Berücksichtigung des Tötungsdelikts im Jahr 1999 selbst vornehme und die Frage nicht einem psychiatrischen Sachverständigen unterbreite, der über das notwendige Fachwissen verfüge.
2.2. Die Vorinstanz erwägt, der Beschwerdegegner habe mit der qualifizierten Vergewaltigung eine im Deliktskatalog von <ref-law> aufgeführte Tat begangen und dadurch das Opfer in seiner sexuellen Integrität schwer beeinträchtigt. Der psychiatrische Gutachter habe beim Beschwerdegegner eine dissoziale Persönlichkeitsproblematik und eine zeitlich stabile Tendenz zu deliktischem sowie insbesondere auch gewalttätigem Verhalten festgestellt. Dies lasse mit hoher Wahrscheinlichkeit weitere und auch schwerwiegende Gewaltstraftaten erwarten. Die therapeutischen Möglichkeiten, die Kriminalprognose in einem Zeitraum von fünf Jahren effektiv zu verbessern, seien gering. Sodann verneine der Gutachter das Vorliegen einer schweren psychischen Störung im Sinne von Art. 59 und 63 StGB. Auch würden sich wegen der fehlenden Bereitschaft des Beschwerdegegners, sich mit dem eigenen Fehlverhalten kritisch auseinanderzusetzen, der fehlenden Behandlungsmotivation, dem hohen Ausprägungsgrad von "psychopathy"-Merkmalen und aufgrund des fehlenden Problembewusstseins und Leidensdrucks keine konkreten Erfolgsaussichten einer psychotherapeutischen Intervention skizzieren. Der Sachverständige habe sowohl in seinem Gutachten vom 12. Juli 2012 als auch im Ergänzungsgutachten vom 25. Juli 2013 hervorgehoben, dass der Beschwerdegegner an einer dissozialen Persönlichkeitsstörung leide, die zusammen mit den "psychopathy"-Merkmalen für die Kriminalprognose von grosser Bedeutung seien. Der Gutachter komme zum Schluss, aufgrund der dissozialen Persönlichkeitsmerkmale und zahlreicher weiterer Risikomerkmale für rezidivierende Gewalt- und Sexualdelinquenz sei ernsthaft zu erwarten, dass der Beschwerdegegner weitere und auch schwerwiegende Gewaltstraftaten begehen werde. Die vom Gutachter angestellten Überlegungen und die daraus zur Frage der Verwahrung abgeleiteten Schlussfolgerungen seien grundsätzlich schlüssig und nachvollziehbar. Es bestünden keinerlei Anhaltspunkte, dass das Gutachten nicht lege artis erstellt worden sei.
Vorliegend sei jedoch zu berücksichtigen, dass der Beschwerdegegner die schwerwiegendsten Delikte als Jugendlicher verübt habe. Er sei mit Urteil des Jugendgerichts des Bezirks Affoltern vom 5. Oktober 2000 wegen vorsätzlicher Tötung, Raubes und Diebstahls in ein Erziehungsheim im Sinne von Art. 91 Ziff. 2 aStGB eingewiesen worden und es sei eine besondere Behandlung angeordnet worden. Dieses Urteil sei von Amtes wegen im Oktober 2010 aus dem Strafregister gelöscht worden. Nach <ref-law> dürfe ein entferntes Urteil dem Täter nicht mehr entgegengehalten werden. Gemäss der bundesgerichtlichen Rechtsprechung dürften entfernte Urteile daher weder bei der Strafzumessung noch bei der Prognosebeurteilung zulasten des Betroffenen verwendet werden. Für die Legalprognose solle mit anderen Worten nicht erlaubt sein, ein Kapitalverbrechen miteinzubeziehen, das zwölf Jahre vor dem zu beurteilenden Delikt verübt wurde. Das Tötungsdelikt aus dem Jahre 1999 werde vom Gutachter einlässlich abgehandelt und habe offensichtlich bei der medizinischen Prognosestellung, zusammen mit dem Raubüberfall, den der Beschwerdegegner als Jugendlicher verübt habe, erhebliche Bedeutung gehabt. Dies werde insbesondere daraus deutlich, dass der Gutachter ausführe, er habe ohne die ausführlichen Vorbefunde zu keinem Zeitpunkt an das Bestehen einer emotional-instabilen Persönlichkeitsstörung gedacht; zudem könne man diese Diagnose auch anhand der Angaben des Beschwerdegegners aktuell nicht stellen. Zusammenfassend führe der Gutachter aus, beim Beschwerdegegner könne eine dissoziale Persönlichkeitsstörung diagnostiziert werden. Jedoch sei davon auszugehen, dass diese im Jugendalter und jungen Erwachsenenalter eine wesentlich deutlichere Ausprägung gehabt habe als aktuell. Die Auswirkungen der Persönlichkeitsstörung auf die psychosoziale Leistungsfähigkeit des Beschwerdegegners seien aktuell nicht als gravierend einzuschätzen. Auch dies ist nach Ansicht der Vorinstanz ein klarer Hinweis auf die dominierende Bedeutung des Tötungsdelikts in der psychiatrischen Begutachtung.
Die Vorinstanz gelangt zum Schluss, dass die wesentlichen Umstände des Tötungsdelikts zwar bei der Realprognose berücksichtigt werden dürften bzw. müssten, bei der Legalprognose indessen nach dem gesetzgeberischen Willen ausgeblendet werden müssten. Eine allfällige Schlechtprognose dürfe somit nur im Umfang der noch eingetragenen Vorverurteilungen berücksichtigt werden. Wie dargelegt, kämen dem Raub und den beiden Versuchen hierzu im Vergleich zum Tötungsdelikt klarerweise eine stark untergeordnete Bedeutung zu, weshalb es sich nicht rechtfertige, gestützt darauf die härteste Massnahme, die Verwahrung anzuordnen. Es gebe daher unter der heutigen Rechtslage keine andere Möglichkeit, als von einer Verwahrung abzusehen (Urteil S. 16 ff.).
2.3. Gemäss <ref-law> ist eine Massnahme anzuordnen, wenn eine Strafe allein nicht geeignet ist, der Gefahr weiterer Straftaten des Täters zu begegnen (lit. a), ein Behandlungsbedürfnis des Täters besteht oder die öffentliche Sicherheit dies erfordert (lit. b) und die Voraussetzungen der Artikel 59-61, 63 oder 64 erfüllt sind (lit. c). Die Anordnung einer Massnahme setzt voraus, dass der mit ihr verbundene Eingriff in die Persönlichkeitsrechte des Täters im Hinblick auf die Wahrscheinlichkeit und Schwere weiterer Straftaten nicht unverhältnismässig ist (<ref-law>). Das Gericht stützt sich bei seinem Entscheid über die Anordnung einer therapeutischen Massnahme auf eine sachverständige Begutachtung (<ref-law>; <ref-ruling> E. 4.3.1 S. 326; vgl. auch <ref-law>). Das Gutachten muss sich über die Notwendigkeit und die Erfolgsaussichten einer Behandlung des Täters (lit. a), die Art und die Wahrscheinlichkeit weiterer möglicher Straftaten (lit. b) und die Möglichkeiten des Vollzugs der Massnahme (lit. c) äussern. Auch wenn das gerichtlich eingeholte Gutachten grundsätzlich der freien Beweiswürdigung unterliegt, darf das Gericht in Fachfragen nicht ohne triftige Gründe von ihm abrücken und muss Abweichungen begründen (<ref-ruling> E. 6.1 S. 372 f.).
Hat der Täter eine unter <ref-law> fallende Straftat verübt, so ordnet das Gericht gemäss <ref-law> die Verwahrung an, wenn auf Grund der Persönlichkeitsmerkmale des Täters, der Tatumstände und seiner gesamten Lebensumstände ernsthaft zu erwarten ist, dass er weitere Taten dieser Art begeht. Sind die Voraussetzungen sowohl für eine Strafe wie für eine Massnahme erfüllt, so ordnet das Gericht gemäss <ref-law> beide Sanktionen an. Der Vollzug der Freiheitsstrafe geht der Verwahrung voraus (<ref-law>; <ref-ruling> E. 2.3.1 S. 58 f.).
2.4.
2.4.1. Nach <ref-law> dürfen dem Betroffenen aus dem Strafregister entfernte Verurteilungen durch das Gericht nicht mehr entgegen gehalten werden. Das Bundesgericht setzte sich in einem amtlich publizierten Entscheid (<ref-ruling>) ausführlich mit dieser Bestimmung auseinander. Es gelangte zum Schluss, dass nach Ablauf der grosszügig bemessenen Entfernungsfristen die Rehabilitierungs- und Resozialisierungsinteressen des Betroffenen von Gesetzes wegen schwerer zu gewichten sind als die öffentlichen Informations- und Strafbedürfnisse (a.a.O., E. 2.4 S. 91 f.). Daraus folgt allerdings nicht, dass medizinische Sachverständige solche Verurteilungen nicht mehr berücksichtigen dürfen. Erfahren forensische Psychiater im Rahmen ihrer Exploration von inzwischen entfernten Vorstrafen oder sind ihnen solche aus früheren Behandlungen bekannt, so können sie diese bei ihrer Begutachtung nicht ausblenden, ohne ein kunstfehlerbehaftetes medizinisches Urteil abzugeben. Im Gegensatz zu den Strafbehörden dürfen die medizinischen Gutachter somit aktenkundige Hinweise auf entfernte Strafen berücksichtigen. Es ist insofern zwischen medizinischer Realprognose und gerichtlicher Legalprognose zu unterscheiden. Die medizinische Realprognose gibt die Rückfallgefahr des Täters in Berücksichtigung seines gesamten Vorlebens wieder, während die Legalprognose im Sinne von <ref-law> ("auf Grund der Persönlichkeitsmerkmale des Täters, der Tatumstände und seiner gesamten Lebensumstände ernsthaft zu erwarten ist, dass er weitere Taten dieser Art begeht") als Rechtsfrage gerichtlich zu beurteilen ist. Um eine Umgehung des gerichtlichen Verwertungsverbots gemäss <ref-law> zu verhindern, muss aus dem Gutachten hervorgehen, inwiefern die frühere (aus dem Strafregister entfernte) mit der neu zu beurteilenden Delinquenz im Zusammenhang steht (Konnexität) und wie stark sich die aus dem Strafregister entfernten Taten noch realprognostisch auswirken (Relevanz). So kann auch für die gerichtliche Beurteilung gewährleistet werden, dass allfällige Schlechtprognosen nur im Umfang der noch eingetragenen Vorstrafen berücksichtigt werden (vgl. a.a.O., E. 2.5 S. 92 f.; Urteil 6B_240/2017 vom 6. Juni 2017 E. 1.5.3; je mit Hinweisen).
An dieser Rechtsprechung hielt das Bundesgericht wiederholt fest (Urteile 6B_240/2017 vom 6. Juni 2017 E. 1.5.3; 6B_229/2017 vom 20. April 2017 E. 3.4.2; 6B_1339/2016 vom 23. März 2017 E. 1.1.3; 6B_274/2010 vom 3. Mai 2010 E. 1.3 und 1.5). Es besteht kein Anlass auf die bundesgerichtliche Rechtsprechung zurückzukommen (vgl. jedoch de lege ferenda: Art. 34 des Bundesgesetzes vom 17. Juni 2016 über das Strafregister-Informationssystem VOSTRA [noch nicht in Kraft; BBl 2016 4888]; Botschaft vom 20. Juni 2014 zum Strafregistergesetz, BBl 2014 5776 ff. Ziff. 2.3.1 Art. 39).
2.4.2. Soweit die Beschwerdeführerin argumentiert, "die für die Einträge im Erwachsenenstrafrecht entwickelten Regeln" könnten nicht uneingeschränkt auf jugendstrafrechtliche Verurteilungen angewendet werden, übersieht sie, dass das Bundesgericht in seinem Grundsatzentscheid die Verwertung von nicht im Strafregister enthaltenen beziehungsweise daraus entfernter Jugendstrafen zu beurteilen hatte. Folglich wurden die Regeln nicht im Erwachsenenstrafrecht, sondern im Zusammenhang mit Jugendstrafen entwickelt. Dabei hat das Bundesgericht berücksichtigt, dass jugendstrafrechtliche Urteile teilweise bereits nach zehn Jahren entfernt werden (<ref-ruling> E. 2.1 S. 90). Die Beschwerdeführerin zeigt nicht auf, weshalb die bundesgerichtliche Rechtsprechung überprüft werden sollte (vgl. Beschwerde S. 6).
2.4.3. Begründet ist demgegenüber die Rüge der Beschwerdeführerin, die Vorinstanz verletze <ref-law>, indem sie ohne entsprechende Fachkenntnisse und in Abweichung der gutachterlichen Ausführungen die Rückfallgefahr selbst einschätze. Der Beschwerdegegner hat sich vor den zu beurteilenden Delikten mehrfach strafbar gemacht. Mit Urteil des Jugendgerichts des Bezirks Affoltern vom 5. Oktober 2000 wurde er wegen vorsätzlicher Tötung, Raubes und Diebstahls in ein Erziehungsheim eingewiesen (Urteil S. 19). Dieses Urteil wurde im Oktober 2010 aus dem Strafregister gelöscht und darf gemäss <ref-law> bei der Legalprognose nicht mehr berücksichtigt werden. Ferner wurde er am 23. März 2006 wegen Raubes (mehrfacher Versuch), Sachbeschädigung und Übertretung des Betäubungsmittelgesetzes zu einer Zuchthausstrafe von 21⁄2 Jahren verurteilt. Diese Vorstrafe ist im Strafregister aufgeführt und darf dem Beschwerdegegner entgegengehalten werden (vgl. Urteil S. 14; kantonale Akten, act. 438). Dass der Gutachter auch die aus dem Strafregister entfernte Vorstrafe bei der Realprognose mitberücksichtigt, ist nicht zu beanstanden. Jedoch müsste nach der dargelegten Rechtsprechung aus dem Gutachten hervorgehen, inwiefern die Tötung, der Raub und der Diebstahl aus dem Jahr 1999 mit den neu zu beurteilenden (und den jüngeren, noch im Strafregister aufgeführten) Delikten im Zusammenhang stehen und wie stark sie sich noch realprognostisch auswirken. Diese Differenzierung hat der Sachverständige soweit ersichtlich weder im Gutachten noch im Ergänzungsgutachten vorgenommen. Indem die Vorinstanz das psychiatrische Gutachten selbständig analysiert und zum Schluss gelangt, der Raub und die Raubversuche hätten im Vergleich zum Tötungsdelikt klarerweise eine stark untergeordnete Bedeutung, weshalb es sich nicht rechtfertige, gestützt darauf die Verwahrung anzuordnen, masst sie sich psychiatrische Fachkenntnisse an und verletzt Bundesrecht. Die Konnexität und die realprognostische Relevanz der aus dem Strafregister entfernten Delinquenz sind eindeutig psychiatrische Fachfragen, die von einem psychiatrischen Sachverständigen zu beantworten sind. Die Vorinstanz wird die entsprechenden Fragen einer sachverständigen Person unterbreiten (vgl. <ref-law>) und gestützt auf das (Ergänzungs-) Gutachten neu über die Anordnung der Verwahrung befinden müssen. Ob es sich hierbei um einen "unbefassten Sachverständigen" handeln muss, wie dies der Beschwerdegegner verlangt, ist von der Vorinstanz zu entscheiden. Vorliegend ist einzig zu präzisieren, dass die aus dem Strafregister entfernte Delinquenz entgegen der beschwerdegegnerischen Ansicht nicht von der psychiatrischen Beurteilung ausgeschlossen ist. Vielmehr hat der Sachverständige gemäss der dargelegten Rechtsprechung des Bundesgerichts aufzuzeigen, inwiefern die aus dem Strafregister entfernte mit der neu zu beurteilenden (und der nicht entfernten) Delinquenz im Zusammenhang steht und wie stark sich die aus dem Strafregister entfernten Taten noch realprognostisch auswirken.
3.
Die Beschwerde ist teilweise gutzuheissen, Dispositivziffer 3 des obergerichtlichen Urteils aufzuheben und die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen. Im Übrigen ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann.
Die Parteien werden im Umfang ihres Unterliegens grundsätzlich kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 1 sowie 2 BGG). Da dem Beschwerdegegner für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege und Verbeiständung gewährt wurde, sind keine Kosten zu erheben (Art. 64 Abs. 1 und Art. 66 Abs. 4 BGG). Der Kanton Zürich hat dem Beschwerdegegner für das bundesgerichtliche Verfahren im Umfang seines Obsiegens eine angemessene Entschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG). Diese ist praxisgemäss seinem Rechtsvertreter auszurichten. Im Umfang des Unterliegens ist der Rechtsvertreter des Beschwerdegegners aus der Bundesgerichtskasse zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen, Dispositivziffer 3 des Urteils des Obergerichts des Kantons Zürich vom 18. Oktober 2016 aufgehoben und die Sache zu neuer Beurteilung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Zürich hat dem Rechtsvertreter des Beschwerdegegners, Rechtsanwalt Thomas Schütz, für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 1'500.-- zu bezahlen.
4.
Rechtsanwalt Thomas Schütz wird eine Entschädigung von Fr. 1'500.-- aus der Bundesgerichtskasse ausgerichtet.
5.
Dieses Urteil wird den Parteien, A._ und dem Obergericht des Kantons Zürich, II. Strafkammer, schriftlich mitgeteilt.
Lausanne, 16. Oktober 2017
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Andres