Recursivitatea - forma particulara de exprimare a metodei Back-Tracking

Asa cum am amintit deja, aceasta metoda de programare poate fi privita ca forma particulara de exprimare a metodei Back-Tracking. Cu toate acestea, cei ce cunosc istoria informaticii si originile programarii stiu ca aceasta metoda are totusi un caracter special. Aceste lucruri dorim sa le evidentiem in continuare.

Inca inainte de aparitia primului calculator si, deci implicit a oricarei tehnici de programare, unii matematicieni erau profund preocupati de notiunea de calculabilitate. Aceasta notiune ii putea ajuta in efortul lor deosebit de a fundamenta notiunea elementara de algoritm sau metoda automata de calcul. In paralel, cele mai valoroase rezultate le-au obtinut latino-americanul Alonso Church si englezul Alan Turing. In timp ce Turing a introdus pentru algoritm modelul matematic abstract cunoscut sub numele de Masina Turing (care sta la bazele modelului actual de calculator), Church a fundamentat notiunea de metoda de calcul sau calculabilitatea pe functiile recursive. Astfel, teza lui Church afirma ca orice functie definita pe domeniul numerelor naturale este calculabila daca si numai daca ea este recursiva. Desi aparatul teoretic folosit de Church era in intregime matematic (se baza numai pe functii numerice naturale), lui nu i-a fost greu sa demonstreze ca orice algoritm nenumeric se reduce la functii recursive si la multimi recursive de numere naturale (pe baza unor codificari riguros alese).

Acest din urma rezultat este cel care ne intereseaza pe noi si noi il vom reformula fara ai afecta valabilitatea: orice algoritm poate fi rescris printr-un algoritm recursiv (limbajul de programare Lisp se bazeaza in intregime pe acest fapt). Chiar daca nu constituie o demonstratie riguroasa, urmatoarea echivalenta practica (descrisa in pseudo-cod) este deosebit de convingatoare: orice instructiune de ciclare este echivalenta cu un apel recursiv de subprogram sau functie.

Observam ca in cazul variantei recursive conditia de scurt-circuitare a recursivitatii este echivalenta conditiei de scurt-circuitare a ciclului. Gestiunea contorului se face in acest caz in back-ground, prin mecanismul de stiva sistem.

Putem astfel concluziona: toti algoritmii iterativi pot fi inlocuiti prin algoritmi recursivi. Avantajul celor recursivi este dat de scaderea dimensiunilor programelor si de cresterea lizibilitatii. Avantajul celor iterativi este viteza marita de executie prin gestionarea locala a parametrilor de ciclare (eliminindu-se astfel toate instructiunile push si pop pentru gestionarea stivei).

Spre edificare, va oferim in continuare citeva probleme clasice (simple) rezolvate in C prin metoda recursiva. In capitolul cu probleme ce necesita back-tracking veti gasi si alte solutii recursive (in C) ale unor probleme ceva mai dificile; astfel se vor putea sesiza mai bine avantajele acestei metode 'naturale' de programare. (Intrucit am considerat acest capitol ca fiind destul de 'tehnic', prezentam in continuare doar variantele de program in limbajul C, ce este considerat mai 'tehnic' decit limbajul Pascal.)

Proiect: Fisa de lucru - operatii cu numere intregi Referat: Jocuri didactice matematica - lantul buclucas

1. Sa se copieze un sir de caractere intr-altul.

#include <stdio.h>

char *sir1='primul',*sir2='al doilea';

void strcopy(char *sursa,char *dest)

void main(void)

2. Sa se afiseze primele n patrate perfecte.

#include <stdio.h>

#include <math.h>

int n;

void patrat(int m)

void main(void)

3.Algoritmul lui Euclid.

#include <stdio.h>

int cmmdc(int m,int n)

void main(void)

4. Se citeste n, sa se gaseasca primul numar prim mai mare decit n. (Se presupune cunoscuta demonstratia faptului ca exista p-prim mai mare decit oricare n. Sintem astfel siguri ca algoritmul se opreste! )

#include <stdio.h>

#include <math.h>

int n;

int are_divizor(int p,int d)

void prim(int p)

else prim(p+1);

void main()

5. Sa se afiseze primele n numere prime.

#include <stdio.h>

#include <math.h>

int n;

int are_divizor(int p,int d)

void prim(int p,int i)

else prim(p+1,i);

void main()

6. Se citeste n gradul unui polinom P si a[0],a[1],,a[n] coeficientii reali ai acestuia. Se citeste o valoare reala x, sa se calculeze P(x).

#include <stdio.h>

int n;

float a[20],x;

float P(int i)

void citeste_coef(int i)

void main()

7. Se citesc m si n gradele a doua polinoame P si Q, si a[0],a[1],,a[m] respectiv b[0],b[1],,b[n] coeficientii reali ai acestora. Sa se afiseze coeficientii c[0],c[1],,c[m+n] ai polinomului produs R=PxQ.

#include <stdio.h>

int m,n;

float a[20],b[20],c[40];

float suma_prod(int i,int j)

void calc_coef(int i)

void citeste_coef(float a[],int i)

void afis_coef(float a[],int i)

void main()

8. Se citeste n, o valoarea intreaga pozitiva, sa se determine suma cifrelor lui n.

#include <stdio.h>

int n;

int suma(int n)

void main()