10
Ich wurde in einem Interview gefragt, der effiziente Weg, um ein Problem für Pallindrome zu lösen.Raumkomplexität des rekursiven Algorithmus
Jetzt kann ich zwei Dinge tun:
- von i = 0 bis i = n/2 und Vergleichen i-ten und n-i-te Zeichen gleich sein zu starten.
- Ich kann Rekursion verwenden, um zu überprüfen, ob die erste und die letzte gleich sind und der Rest der Zeichenfolge ist ein Pallindrome.
Die zweite ist rekursiv. Meine Frage ist, was ist der Unterschied in der Raumkomplexität der rekursiven und nicht-rekursiven Versionen eines Algorithmus?
Bei großen Datensätzen, selbst bei Tail-Rekursion, führt dies zu StackOverflow-Fehlern. Nein? – Sudhakar
@Sudhakar Das ist genau das, was die Tail Recursion-Optimierung verhindert :) –
Ist dieses Programm ein gültiges Beispiel für Tail Recursion. Dies erzeugt stackoverflow. Pls korrigieren Sie mich, wenn iam falsch ist.
public class TailTest { \t public static void main(String[] args) { \t \t System.out.println(TailTest.iterate(100000)); \t } \t \t public static long iterate(int n){ \t \t if(n==1) return 1; \t \t \t \t return iterate(n-1); \t } }– Sudhakar