Diferència clau: recursivitat versus iteració
La recursència i la iteració es poden utilitzar per resoldre problemes de programació. L'enfocament per resoldre el problema mitjançant recursivitat o iteració depèn de la manera de resoldre el problema. La diferència clau entre recursivitat i iteració és que la recursió és un mecanisme per cridar una funció dins de la mateixa funció, mentre que la iteració és executar un conjunt d'instruccions repetidament fins que la condició donada sigui certa. La recursió i la iteració són tècniques principals per desenvolupar algorismes i crear aplicacions de programari.
Què és la recursió?
Quan una funció s'anomena dins de la funció, es coneix com a recursència. Hi ha dos tipus de recursivitat. Són recursivitat finita i recursivitat infinita. La recursivitat finita té una condició final. La recursivitat infinita no té una condició final.
La recursència es pot explicar mitjançant el programa per calcular factorials.
n!=n(n-1)!, si n>0
n!=1, si n=0;
Consulteu el codi següent per calcular el factorial de 3(3!=321).
intmain () {
int valor=factorial (3);
printf(“El factorial és %d\n”, valor);
retorn 0;
}
intfactorial (intn) {
if(n==0) {
retorn 1;
}
else {
retorn n factorial(n-1);
}
}
Quan es crida a factorial (3), aquesta funció cridarà a factorial (2). En cridar factorial (2), aquesta funció cridarà factorial (1). Aleshores, el factorial (1) anomenarà factorial (0). el factorial (0) retornarà 1. Al programa anterior, la condició n==0 al "bloc if" és la condició base. Segons el mateix, la funció factorial s'anomena una i altra vegada.
Les funcions recursives estan relacionades amb la pila. En C, el programa principal pot tenir moltes funcions. Per tant, main () és la funció crida, i la funció cridada pel programa principal és la funció cridada. Quan es crida la funció, el control es dóna a la funció cridada. Un cop finalitzada l'execució de la funció, el control es torna a principal. Després continua el programa principal. Per tant, crea un registre d'activació o un marc de pila per continuar amb l'execució.
Figura 01: recursivitat
Al programa anterior, quan es crida al factorial (3) des de main, es crea un registre d'activació a la pila de trucades. Aleshores, es crea un marc de pila factorial (2) a la part superior de la pila i així successivament. El registre d'activació guarda informació sobre variables locals, etc. Cada vegada que es crida a la funció, es crea un nou conjunt de variables locals a la part superior de la pila. Aquests marcs de pila poden alentir la velocitat. De la mateixa manera, en recursivitat, una funció s'anomena a si mateixa. La complexitat del temps per a una funció recursiva es troba pel nombre de vegades que s'anomena la funció. La complexitat temporal per a una crida de funció és O(1). Per a n nombre de trucades recursives, la complexitat temporal és O(n).
Què és la iteració?
La iteració és un bloc d'instruccions que es repeteix una i altra vegada fins que la condició donada es compleix. La iteració es pot aconseguir mitjançant "bucle for", "bucle do-while" o "bucle mentre". La sintaxi "for loop" és la següent.
per a (inicialització; condició; modificar) {
// declaracions;
}
Figura 02: "diagrama de flux de bucle"
El pas d'inicialització s'executa primer. Aquest pas és declarar i inicialitzar variables de control de bucle. Si la condició és certa, s'executen les declaracions dins de les claus. Aquestes declaracions s'executen fins que la condició és certa. Si la condició és falsa, el control passa a la següent instrucció després del "bucle for". Després d'executar les instruccions dins del bucle, el control passa a la secció de modificació. És per actualitzar la variable de control de bucle. A continuació, es torna a comprovar la condició. Si la condició és certa, s'executaran les declaracions dins de les claus. D'aquesta manera, el "bucle for" itera.
A "bucle mentre", les declaracions dins del bucle s'executen fins que la condició es compleix.
mentre (condició){
//declaracions
}
En el bucle "do-while", la condició es comprova al final del bucle. Per tant, el bucle s'executa almenys una vegada.
fer{
//declaracions
} mentre(condició)
El programa per trobar el factorial de 3 (3!) mitjançant la iteració ("bucle for") és el següent.
int main(){
intn=3, factorial=1;
inti;
for(i=1; i<=n; i++){
factorial=factoriali;
}
printf(“Factorial és %d\n”, factorial);
retorn 0;
}
Quines similituds hi ha entre la recursió i la iteració?
- Totes dues són tècniques per resoldre un problema.
- La tasca es pot resoldre en recursivitat o en iteració.
Quina diferència hi ha entre la recursió i la iteració?
Recursió versus iteració |
|
| La recursència és un mètode per cridar una funció dins de la mateixa funció. | La iteració és un bloc d'instruccions que es repeteix fins que la condició donada es compleix. |
| Complexitat de l'espai | |
| La complexitat espacial dels programes recursius és superior a les iteracions. | La complexitat de l'espai és menor en iteracions. |
| Velocitat | |
| L'execució de la recursió és lenta. | Normalment, la iteració és més ràpida que la recursivitat. |
| Condició | |
| Si no hi ha cap condició de terminació, pot haver-hi una recursivitat infinita. | Si la condició mai esdevé falsa, serà una iteració infinita. |
| Pila | |
| En recursivitat, la pila s'utilitza per emmagatzemar variables locals quan es crida la funció. | En una iteració, la pila no s'utilitza. |
| Llegibilitat del codi | |
| Un programa recursiu és més llegible. | El programa iteratiu és més difícil de llegir que un programa recursiu. |
Resum – Recursió versus iteració
Aquest article parla de la diferència entre recursivitat i iteració. Tots dos es poden utilitzar per resoldre problemes de programació. La diferència entre recursivitat i iteració és que la recursió és un mecanisme per cridar una funció dins de la mateixa funció i iterar-la per executar un conjunt d'instruccions repetidament fins que la condició donada sigui certa. Si un problema es pot resoldre de forma recursiva, també es pot resoldre mitjançant iteracions.
Descarregueu la versió PDF de Recursió vs Iteració
Podeu baixar la versió PDF d'aquest article i utilitzar-la per a finalitats fora de línia segons la nota de citació. Si us plau, descarregueu la versió PDF aquí Diferència entre recursió i iteració
