Rekursive Funktionen

newprogrammer1996

newprogrammer1996 schrieb:

Hallo ich muss ein Programm schreiben, dass eine umgekehrte Zeichenfolge ausgibt also zB.: Eingabe:"hallo" Ausgabe: "ollah". Dabei muss ich auch eine Funktion schreiben und keine Schleifen verwenden. Ich darf jedoch nur den string übergeben also wenn ich jetzt in der Funktion eine Variable deklariere/initialisiere wird sie ja immer wieder auf den ursprünglichen Wert zurückgesetzt. Also wie könnte ich das verhindern? Vielen Dank im Voraus ! (Ich würde es gerne ohne globalen Variablen, Pointern und Referenzen programmieren)

Beispiel:
string f2(string zeichenkette)
{
  string neue_zeichenkette;
  int x = 0;
  if(x >= zeichenkette.length()){return neue_zeichenkette;}
  else neue_zeichenkette += zeichenkette.length(x);
  f2(zeichenkette, x+1);

}

sorry mir sind da viele fehler eingeschlichen hier die verbesserte (trotzdem nicht richtige Funktion:

string f2(string zeichenkette, int x)
{
string neue_zeichenkette;
if(x <= 0)
{
neue_zeichenkette += zeichenkette.at(x);
f2(zeichenkette, x-1);
}
return neue_zeichenkette;
}

newprogrammer1996

SeppJ schrieb:

Die lokalen Variablen in der Funktion sind bei jedem Aufruf neue Variablen. Wenn du die Funktion innerhalb der Funktion selber noch einmal aufrufst, hat dieser neue Aufruf neue lokale Variablen. Und die Variablen im alten Aufruf bleiben erhalten. Also kein Problem.

Lass das x weg. Eine viel einfachere, rekursive Definition einer umgedrehten Zeichenfolge ist: Eine umgedrehte Zeichenfolge ist leer, falls das Original leer ist. Ansonsten ist sie das letzte Zeichen der Originalfolge plus die Umdrehung aller Zeichen der Originalfolge vor dem letzten Zeichen.

Wie du siehst, muss da nirgendwo gezählt werden, alles geht über Zeichenfolgen und ihre Längen.

Danke ich verstehe trotzdem nicht wie ich es in einer (rekursiven?) Funktion ohne Schleifen verpacke wo ich eben nur einen (den ursprünglichen) string übergeben kann

SG1

Indem Du es so machst, wie SeppJ beschrieben hat. Hast Du da konkretere Fragen zu?

temi

SeppJ schrieb:

Ansonsten ist sie das letzte Zeichen der Originalfolge plus die Umdrehung aller Zeichen der Originalfolge vor dem letzten Zeichen.

Versuch dir das mal so vorzustellen:

"HALLO" => "O" + Umdrehen("HALL")

Schrittweise soll passieren:

rückwärts("hallo") = rückwärts("allo") + "h"
rückwärts("allo") = rückwärts("llo") + "a"
rückwärts("llo") = rückwärts("lo") + "l"
rückwärts("lo") = rückwärts("o") + "l"
rückwärts("o") = "o"

Alternativ gehts auch andersrum (SeppJs Vorschlag, meiner Meinung nach etwas schwieriger):

rückwärts("hallo") = "o" + rückwärts("hall")
rückwärts("hall") = "l" + rückwärts("hal")
...
rückwärts("h") = "h"

Das = ist hier für dich als "soll zurückgeben" zu lesen.

Um aus "hallo" "allo" oder "hall" zu machen, schau dir mal http://www.cplusplus.com/reference/string/string/substr/ an.

temi

newprogrammer1996 schrieb:

Danke ich verstehe trotzdem nicht wie ich es in einer (rekursiven?) Funktion ohne Schleifen verpacke wo ich eben nur einen (den ursprünglichen) string übergeben kann

Das funktioniert, weil du bei einem "return" immer zum jeweils letzten Aufruf zurückspringst und wie SeppJ schon geschrieben hat, sind dort die Variablen noch mit ihren Werten vorhanden.

Ansonsten schau dir auf jeden Fall die Referenz zum "string" an, der bietet viele nützliche Funktionen:

back(), front() => letzten, bzw. ersten Zeichen des Strings
push_back(), append() => String, Zeichen anhängen
pop_back() => letztes Zeichen löschen

There's more than one way to skin a cat.

Muss es unbedingt rekursiv sein?

Swordfish

Schön wie wieder mal eine sinnfreie Aufgabe Forenseiten füllt

#include <iterator>
#include <algorithm>
#include <string>
#include <iostream>

int main()
{
	std::string str{ "Hello!" };
	std::copy( str.rbegin(), str.rend(), std::ostream_iterator< char >{ std::cout } );
}

vll hilf dir das hier:
http://www.willemer.de/informatik/cpp/rekursion.htm
(hoff ist ok, das ich einen link poste...)

lg

Andromeda

Simpelste Lösung:

#include <iostream>

void print (char *str)
{
    if (*str)
        print(str+1);
    std::cout << *str;
}

int main()
{
    print ("hallo");
}

DirkB

Andromeda schrieb:

Simpelste Lösung:

#include <iostream>

void print (char *str)
{
    if (*str)
        print(str+1);
    std::cout << *str;
}

int main()
{
    print ("hallo");
}

C-Strings sind super

Igitt, Zeiger char*. Frei nach SeppJ :

#include <string>

std::string f2(const std::string& str) {
  if (str.length() == 0) {
    return str;
  }
  else {
    return str.substr(str.length()-1)  // letztes Zeichen als String
      + f2(str.substr(0, str.length()-1));    // der umgedrehte Rest
  }
}

int main() {
  std::cout << f2("Hallo") << '\n';
}

scheint mir angemessener zu sein in Bezug auf die Aufgabenstellung.

Andromeda

DirkB schrieb:

Andromeda schrieb:

Simpelste Lösung:

#include <iostream>

void print (char *str)
{
    if (*str)
        print(str+1);
    std::cout << *str;
}

int main()
{
    print ("hallo");
}

C-Strings sind super

Bei C ist alles super. Sogar das doofe, C++-mäßige *std::cout << str; kann man durch *putchar (str); ersetzen.

EOP

A bit of spoon feeding because it is sunday:

int main(void)
{
	string str = "Hello World";
	rek( str, static_cast<int>(str.length())-1 );
	return 0;
}

void rek(string str, int len)
{
	if( len >= 0 )
	{
		cout << str.at(len);
		rek(str, len-1);
	}	
}

EOP schrieb:

A bit of spoon feeding because it is sunday:

int main(void)
{
	string str = "Hello World";
	rek( str, static_cast<int>(str.length())-1 );
	return 0;
}

void rek(string str, int len)
{
	if( len >= 0 )
	{
		cout << str.at(len);
		rek(str, len-1);
	}	
}

static_cast ist bei richtigem Parametertyp überflüssig. Zwei Parameter statt einem == unelegant. cout in der Funktion ist ganz schlecht, weil du die Funktionalität "Ausgabe" mit der Funktionalität "String umdrehen" in eine einzige Funktion packst. Eine Funktion zum Umdrehen sollte auch in einer GUI nutzbar sein. Dies nur als "spoon feeding" für dich. Schönen Sonntag!

EOP

Hab das in weniger als 2 min. geschrieben - ohne Beachtung der Eleganz.

ohwierekursiv schrieb:

Igitt, Zeiger char*. Frei nach SeppJ :
[...]

Hm, wenns hier schon ne vollständige Lösung gibt, dann hier:

std::string rueckwaerts(const std::string &str) {
    return str.size() < 2 ? str : rueckwaerts(str.substr(1)) + str[0];
}

So herum ists einfacher. Und man kann den Rekursionsabbruch schon bei Länge 1 machen.

DirkB

irrsinnEOP schrieb:

cout in der Funktion ist ganz schlecht, weil du die Funktionalität "Ausgabe" mit der Funktionalität "String umdrehen" in eine einzige Funktion packst.

Die Aufgabe lautete, den String umgekehrt auszugeben.
Wenn man das machen kann, ohne den String zu verändern oder einen neuen anzulegen, hat das auch eine gewisse Eleganz.

Andromeda

ohwierekursiv schrieb:

Igitt, Zeiger char*. Frei nach SeppJ :

#include <string>

std::string f2(const std::string& str) {
  if (str.length() == 0) {
    return str;
  }
  else {
    return str.substr(str.length()-1)  // letztes Zeichen als String
      + f2(str.substr(0, str.length()-1));    // der umgedrehte Rest
  }
}

int main() {
  std::cout << f2("Hallo") << '\n';
}

scheint mir angemessener zu sein in Bezug auf die Aufgabenstellung.

So gehts auch, ohne Zeiger:

#include <iostream>
#include <string>
using namespace std;

void print (string s)
{
    char c = s[0];
    if (s.length())
        print(s.erase(0,1));
    cout << c;
}

int main()
{
    print ("hello");
}

EOP

Ich hätte das wahrscheinlich auch eleganter hingekriegt, aber die Aufgabe war, das rekursiv zu lösen und ich hatte nach 4 Flaschen Merlot nicht mehr soviel Enthusiasmsus.

EDIT: ~~ein~~zwei 's' vergessen