Keskustelu: Ohjelmointikysymykset: Java: Merkkijonon kääntö rekursiolla

(Mod. siirsi rekursio-oppaan kommenteista.)

Törmäsin opettavaisen tuntuiseen esimerkkiin.

#include <iostream>

using namespace std;
void reverse(char *a);
int main(int argc, char *argv[])
{
    char str[] = "This is a test";
    reverse(str);
}
void reverse(char *a){
     if (*a)
        reverse(a+1);
     else
          return;
     cout<< *a;
}

Sitten kokeilin tehdä saman Javalla. Siitä tuli vähän monimutkaisempi, mutta lyhyt.

public class Ohjelma {

    public static void main(String[] args) {
        String str = "hello";
        System.out.println(reverse(str, 0));
    }
    public static String reverse (String instring, int indeksi){
        if (indeksi < instring.length()){
            return reverse(instring, indeksi+1)+instring.charAt(indeksi);
        }
        else return "";
    }
}

Saisko tämän Javalla jotenkin ytimekkäämmäksi? Onko toi kakkosparametri pakko olla?

Koitin hahmotella itselleni pinon toimintaa.

kutsu                      arvo                pinon purkautuessa
                           pinoon mennessä
6. kutsu palauttaa->       ""                  ""
5. kutsu palauttaa->       6. kutsu + o        ""o
4. kutsu palauttaa->       5. kutsu + l        ""ol
3. kutsu palauttaa->       4. kutsu + l        ""oll
2. kutsu palauttaa->       3. kutsu + e        ""olle
1. kutsu palauttaa->       2. kutsu + h        ""olleh
"" tarkoittaa, että mitään ei mene merkkijonoon.
str="hello";
str.length() == reverse(hello, 0).length()

lrp kirjoitti:

Saisko tämän Javalla jotenkin ytimekkäämmäksi? Onko toi kakkosparametri pakko olla?

No ton java-ohjelman saa suoraan käännettyä C++:sta näin:

public static void reverse (String a){
    if (!a.isEmpty()){
        reverse(a.substring(1));
    }
    else return;

    System.out.print(a.charAt(0));
}

Ja niin että se palauttaa merkkijonon:

public static String reverse (String a){
    if (!a.isEmpty()){
        return reverse(a.substring(1))+a.charAt(0);
    }
    else return "";
}

Tyylivalitusta seuraa. Tuo alkuperäinen koodi on kyllä taas hieno esimerkki if-else-rakenteen epäselvästä käytöstä. Koodissa rekursiivinen kutsu ja merkin tulostus kuuluvat kiinteästi yhteen, joten ne olisi viisainta laittaa joko yhdessä if-lauseen sisään tai yhdessä sen ulkopuolelle. Molemmissa tapauksissa else-lohko jää tarpeettomaksi, koska funktiossa halutaan suorittaa joko molemmat olennaiset rivit tai ei kumpaakaan riviä.

Tässä molemmat rivit ovat if-lauseessa eikä else-lohkoa tarvita:

if (*a) {
	reverse(a + 1);
	std::cout << *a;
}

Tässä kumpikaan rivi ei ole if-lauseessa mutta else-lohkoa ei silti tarvita, koska if-lauseen sisällä on return-lause.

if (!*a) {
	return;
}
reverse(a + 1);
std::cout << *a;

Tässä ovat vastaavat koodit Javalla silloin, kun funktio palauttaa merkkijonon:

if (!a.isEmpty()) {
	return reverse(a.substring(1)) + a.charAt(0);
}
return "";

if (a.isEmpty()) {
	return "";
}
return reverse(a.substring(1)) + a.charAt(0);

Tässä on vielä pakollinen yhden rivin versio, ettei kenenkään muun tarvitse sen takia lähettää viestiä:

return a.isEmpty() ? "" : (reverse(a.substring(1)) + a.charAt(0));