DEFINITIA RECURSIVITATII
Recursivitatea reprezinta o tehnica de programare de o importanta deosebita. Ea permite o exprimare extrem de concisa si clara a algoritmilor de rezolvare a unor probleme complexe.
Un subprogram este recursiv daca se apele 131j96b aza pe el insusi (se autoapeleaza).
REALIZAREA AUTOAPELULUI
Consideram urmatorul subprogram:
#include<iostream.h>
void exemplu (int n)
void main()
Se observa ca tipul functiei este de tip void si deci nu returneaza nici o valoare. De aceea nu poate fi utilizata in calcului unei expresii
Parametrul efectiv 3 este memorat in segmentul de stiva. Pe parcursul rularii programului stiva va contine:
Programul afiseaza:
In cazul acestui program
#include<iostream.h>
int suma(int n)
void main()
Desi in stiva sunt introduse si apoi extrase aceleasi elemente, functia fiind de tip int poate fi utilizata in expresia ce va fi returnata si astfel putem calcula . Programul afiseaza .
Diferenta dintre cele doua subprograme este urmatoarea:
In cazul functiilor de tip void, autoapelul se realizeaza prin apelul functiei respective, din interiorul ei. Apelul se face la fel ca in cazul in care functia este apelata din exterior.
In cazul functiilor care nu sunt de tip void, autoapelul se realizeaza prin instructiunea return. Ea este de forma
return expresie
dar in expresia respectiva trebuie sa intre si functia care se autoapeleaza.
MECANISMUL RECURSIVITATII
Consideram urmatoarea problema:
Sa se calculeze recursiv n!.
Pentru intelegerea notiunii de factorial aleg doi si apoi trei copii si cautam toate posibilitatile de asezare pe 2 sau 3 scaune. De aici, deducem ca
Prin generalizare, obtinem
n!=n*(n-1)!=n*(n-1)*(n-2)!=.=n*(n-1)*(n-2)*.*3*2*1
Definitia
recursiva a lui n! este:
Subprogramul fact transcrie definitia recursiva.
#include<iostream.h>
int fact (int n)
void main()
CUM GANDIM UN ALGORITM RECURSIV?
Ce se intampla la un nivel se intampla la orice nivel.
Subprogramul care se autoapeleaza trebuie sa contina instructiunile corespunzatoare unui nivel.
Starea tratata de subprogram se gaseste pe un anumit nivel al stivei.
Observatii
Pentru orice algoritm recursiv exista unul iterativ care rezolva aceeasi problema.
Nu intotdeauna alegerea unui algoritm recursiv reprezinta un avantaj.
Recursivitatea presupune mai multa memorie in comparatie cu iterativitatea.
|
Intrebare |
Raspuns asteptat |
|
Orice subprogram recursiv se poate implementa si nerecursiv |
A |
|
Functia main () poate contine autoapel. |
F |
|
La fiecare apel recursiv al unui subprogram, in segmentul de stiva sunt memorate a) Adresa de revenire, valorile variabilelor locale si a parametrilor transmisi prin referinta b) Adresa de revenire si valorile variabilelor globale c) Adresa de revenire, valorile variabilelor locale si a parametrilor transmisi prin valoare si adrese parametrilor transmisi prin referinta d) Adresa de revenire, valorile locale si a variabilelor globale |
c) |
|
Fie functia recursiva: int f(int n) Precizati valoarea lui n pentru care f(n)= 36 a) 9 b) 3 c) 15 d) 6 |
d) |
|
