Factorial al unui număr care utilizează recursivitatea

Am funcția recursivă de mai jos pentru a calcula factorialul unui număr. Programul funcționează bine, cu excepția cazului în care elimină condiția if. Poate cineva să explice de ce?

Acesta este codul care funcționează bine -

public static long factUsingRecursion(int number) {
    if (number == 1) {
        return 1;
    } else {
        return number * factUsingRecursion(number - 1);
    }
}

Fără condiția dacă (Codul care aruncă eroarea)

public static long factUsingRecursion(int number) {
    return number * factUsingRecursion(number - 1);
}

Am o eroare de depășire a stivei.

Excepție în firul "principal" java.lang.StackOverflowError   la birst.FactorialUsingRecursion.factUsingRecursion (FactorialUsingRecursion.java:10)

Cereți experților să vă rog să-mi spuneți de ce este cazul?

0
Longs nu se limitează la numere pozitive. Computerele vor face tot ceea ce le spuneți să facă .... deci nu este ca și cum funcția se va opri în mod magic dacă numărul este egal cu 1. Fără instrucțiunea if, dacă apăsați funcția după funcția în stivă, fără o șansă ca oricare dintre afirmații să întoarceți vreodată și încheiați recursiunea. numărul se va îndrepta către infinit negativ până când stivălele vor depăși
adăugat autor sunrize920, sursa
Indiciu: Fără dacă - cum decideți când să opriți?
adăugat autor cpt. jazz, sursa
Puteți alege un răspuns "acceptat" într-o întrebare.
adăugat autor rgettman, sursa
Orice recurzie ar trebui să aibă întotdeauna o condiție de bază pentru a încheia recursiunea. Această condiție este numai pentru condiția de bază. Altfel va deveni o recurență infinită.
adăugat autor Rohit Jain, sursa

7 răspunsuri

În recurs, trebuie să existe întotdeauna un caz de bază care oprește recursiunea. Fără codul dacă , nu aveți niciun caz de bază și nimic nu îl oprește. În cele din urmă prea multe apeluri de metode se află pe stivă și un rezultat StackOverflowError .

7
adăugat
De ce este votat acest lucru?
adăugat autor Rohit Jain, sursa

Această linie care determină variabila number să scadă cu 1

return number * factUsingRecursion(number - 1);

și se va ocupa de toate valorile number cu excepția cazului în care este 1

astfel încât această linie de cod este o condiție de pauză

if (number == 1) {
        return 1;

}

și vă împiedică să evitați excepția stackoverflow

2
adăugat

Imaginați-vă ce se întâmplă când sunați:

factUsingRecursion(3);

Cu:

3*factUsingRecursion(2)
3*2*factUsingRecursion(1)
3*2*1

Fără dacă:

3*factUsingRecursion(2)
3*2*factUsingRecursion(1)
3*2*1*factUsingRecursion(0)
3*2*1*0*factUsingRecursion(-1)
3*2*1*0*-1*factUsingRecursion(-2)
3*2*1*0*-1*-2*factUsingRecursion(-3)
...
And so on... It will not stop until you encounter the StackOverflow error
2
adăugat
@ user2341013 Sunteți bineveniți. btw, pe StackOverflow puteți accepta un singur răspuns (semnul verde), deci alegeți cel care v-a ajutat cel mai mult. Puteți să vă înscrieți (săgeata în sus) cât mai multe răspunsuri, după cum doriți.
adăugat autor Paulpro, sursa
Multumesc mult. Este foarte clar acum. Apreciați răspunsul dvs. rapid!
adăugat autor user2341013, sursa
Sigur, am înțeles. Mulțumesc. În acest caz însă, toate răspunsurile mi-au ajutat;)
adăugat autor user2341013, sursa

Recurgerea necesită un caz de bază. Fără ea, va continua să numească funcția de peste și peste și nu se va opri niciodată. Instrucțiunea if este cazul de bază, care termină recursiunea. De aceea, dacă îl eliminați, veți obține un StackOverflowError .

2
adăugat
De ce a fost votat acest raspuns?
adăugat autor rgettman, sursa

Programul nu va mai funcționa atunci când eliminați condiția if, deoarece va fi lăsat doar cu return number * factUsingRecursion (număr - 1); și factUsingRecursion (număr - 1) aici ar avea aceeași retur apelând returnează numărul * factUsingRecursion (număr - 1); . Funcția dvs. se numește în mod constant, însă nu poate evalua nimic. Prin stabilirea condiției, funcționați puteți evalua la o valoare definitivă la un moment dat în lanțul recursiv și primul apel poate evalua.

1
adăugat

Pierde unul din lucrurile care fac o recursivă funcție recursivă prin faptul că nu are condiție de ieșire.

Toate soluțiile recursive trebuie să satisfacă trei reguli sau proprietăți: O soluție recursivă trebuie să conțină un caz de bază. O soluție recursivă trebuie să conțină un caz recursiv. O soluție recursivă trebuie să facă progrese în cazul de bază.

Din: Structuri de date și algoritmi folosind Python

1
adăugat

Pentru fiecare intreg i, apelați funcția cu i -1. Integersa sunt infinite, deci nu veți înceta niciodată să apelați funcția. de exemplu: -1000 s-ar numi -1001 și acest lucru va continua atât timp cât JVM are ceva spațiu în stack-ul său.

0
adăugat