Rekurencja - odwrotność wyrazu

Question

Czy można napisać krócej moja metodę z rekurencja która ma za zadanie napisać odwrotnie podany wyraz. Mierzyłem czas z wykonaniem tego zadania pętlą i czasy są bardzo zbliżone a czasem nawet pętla ma krótszy czas, więc nie jestem pewien czy wszystko dobrze rozumiem z tą rekurencją.

Czy mógłby mi też ktoś przy okazji dać jakieś zadania z rekurencją?

	public static void main(String[] args) {
	System.out.println("Podaj jakis wyraz: ");
	String wyraz= new Scanner (System.in).nextLine();
     	System.out.println(odwrotnosc(wyraz,wyraz.length()));
	}

	public static char odwrotnosc(String x, int z) {
		if(z==0)
		return 0;
		else {
			System.out.print(x.charAt(z-1));
			return odwrotnosc(x,z-1);
		}
	}

 

Comments

Dlaczego zakładasz, że metoda rekursywna będzie lepsza od iteratywnej?

---

często tak jest, więc myślałem że też tak będzie w tym przypadku

---

Nie wiem jak jest w javie, ale nie skończy Ci się w końcu stos wywołań? Rekursja może wygrywać gdy wchodzi procesor wielordzeniowy, optymalizacje. Jeżli masz procesor, który nie posiada wielu rdzeni, iteracja i rekursja powinny dać podobny efekt. ​​Iteracja jest szybsza niż rekurencja , chociaż w wielu przypadkach, jeśli kod jest dobrze napisany, a kompilator obsługuje "tail call optimization", obie mogą działać równie dobrze.

---

a są jeszcze komputery jednordzeniowe?

---

Czy są? Na pewno są. Czy stanowią większość obecnego rynku? Wątpię.

---

Nie znam się na sprzęcie, ale dlaczego wielordzeniowe procesory miałyby wykonywać rekurencję szybciej? W sensie i tak się musi się to wywołać funkcja po funkcji. Nawet gdyby funkcja odpalała siebie samą kilka razy w swoim ciele to i tak nie możnaby tego odpalić asynchronicznie, bo by się wiele algorytmów zepsuło..

---

Optymalizacyjnie łatwiej jest rozłożyć wywołanie funkcji rekursywnej na wiele rdzeni, niż funkcję iteracyjną.
Wydajność końcowa jest zależna od języka(samego języka jak i wersji, na przykład java od wersji 1.8 wspiera tail call optimization w lambdach), zbioru danych, implementacji. Bez testów wydajnościowych(nie tylko czas, ale i pamięć) nie ma co porównywać mimo wszystko.

---

wystarczy przeklepać zadanie do edytora czasowego jaki mamy np. na Codility :) - gdzie dla pewnych zadań obliczane są złożoności, żeby w prosty sposób sprawdzić, że rekurencja nie jest tutaj szybsza niż metoda iteracyjna i dla większości przypadków tak też się dzieje, przy założeniu sporych ilości danych
Wolno działać będzie bo zauważ że masz System.out.print(x.charAt(z-1));
nie dość że metody dla system.out wywołujesz rekurencyjnie, to jeszcze metody dla zmiennej x.charAt, także reukurencyjnie.

Answer 1

Też to widzę tak : 
 

public static String odwrocWyraz(String pmStr) {
    return !pmStr.equals("") ? odwrocWyraz(pmStr.substring(1)) + pmStr.charAt(0) : pmStr;
}