Iteracja vs Rekurencja

Question

Cześć, nie potrafię logicznie zrozumieć różnicy pomiędzy rekurencją, a iteracją, moje doświadczenie z programowaniem jest równe 0.0001%, jestem bardzo, ale to bardzo zielony. Wiem jedynie tyle, że iteracja to odwoływanie się do początków danej funkcji aby ta mogła się jeszcze raz wykonać aż spełni określony warunek, a rekurencja to wykonywanie funkcji do spełnienia określonego warunku, ale bez "fizycznego" odwoływania się do jej początków, jakim cudem funkcja wie że musi się powtórzyć? Jak tę rekurencję zaznaczyć?

Uczę się w C++

Comments

jakim cudem funkcja wie że musi się powtórzyć? Jak tę rekurencję zaznaczyć?

Bo zwraca samą siebie, a nie konkretną wartość (np. liczbę 5.6). A to że zwraca samą siebie oznacza, że żeby otrzymać wynik, znów musi się wykonać. Czyli funkcja nie zwraca gotowego produktu, tylko przepis jak ten produkt otrzymać.

---

Czyli wynikiem rekurencji jest funkcja sama w sobie? Ma to jakieś zastosowanie? Czy raczej się tego nie używa?

---

Tak, wynikiem jest funkcja, dla której z góry nie znamy argumentu. Na przykład zwrócenie funkcji, która wylicza 2 + 2 nie oznacza rekurencji, bo zawsze ta funkcja zwraca 4.

Rekurencje się stosuje w wielu miejscach, klasykiem jest obliczanie silni danej liczby naturalnej. Rekurencja ma tę zaletę, że taki kod jest krótki i czytelny dla programisty w porównaniu z iteracją. Wadą jest to, że pochłania więcej zasobów niż iteracja.

Answer 1

Witam,

Iteracja (łac. iteratio – powtarzanie) – czynność powtarzania (najczęściej wielokrotnego) tej samej instrukcji (albo wielu instrukcji) w pętli. Mianem iteracji określa się także operacje wykonywane wewnątrz takiej pętli.

Definicja Ci mówi że jest to czynność powtarzania tej samej instrukcji w pętli.

int i=0;
while (i<10) {
  i++;//element iterowany czyli w pierwszej iteracji i = 0, dalej i = 1 i tak do 9
}

Rekurencja, zwana także rekursją (ang. recursion, z łac. recurrere, przybiec z powrotem) – odwoływanie się np. funkcji lub definicji do samej siebie

long long suma(int n)
{
  if(n<1) 
    return 0;
 
  return n+suma(n-1);//odwołanie się do samej siebie(rekurencja)
/*
następnie jeśli argument to umożliwia to zostanie wywołana funkcja 
long long suma(int n - 1) {
 if((n-1)<1) return 0; 
return n+suma((n-1)-1)
i następnie jeśli to możliwe zostanie wywołana funkcja suma(n-2) jeśli jest to możliwe (warunek if). 
*/
}

 

Comments

Cześć, zrobiłem sobie taki kod - chciałem aby sprawdzał czy wartość i jest mniejsza od 10 i jeśli tak to żeby dodawał o 1 i to wypisywał. :) Coś nie gra... Bo po wpisaniu wartości nic się nie dzieję, nawet program nie chcę się zamknąć.

 

#include <iostream>

using namespace std;

int i=0;

int main ()
{
    cout << "Wprowadź wartość i: " << endl;
    cin >> i;
    while (i<10); {
    i++;
    cout << "i";
    }
    return 0;
}

 

---

Witam,

usuń średnik z pętli while()

#include <iostream>
 
using namespace std;
 
int i=0;
 
int main ()
{
    cout << "Wprowadź wartość i: " << endl;
    cin >> i;
    while (i<10) {//stąd usuń ;
    i++;
    cout << "i " << i;// tu jeszcze można dodać 'i' aby //wyświetlało wartość
    }
    return 0;
}

PS.

Unikaj polskich znaków w konsoli bo wtedy wychodzą 'krzaczki'

Answer 2

Prosto mówiąc:

iteracja to pętla, np masz 10 elementów, przechodzisz po kolei po każdym z nich. Albo masz licznik i do spełnienia pewnego warunku wykonujesz zadanie w pętli.

Rekurencja to natomiast gdy funkcja wywołuje samą siebie. Przykłady:

- Iteracja

for(int = 0; i <= 10; i++) std::cout<<i<<endl;

- Rekurencja

int fib(int n)
{
    if(n == 0) return 1;
    else if(n == 1) return 1;
    else return fib(n-1) + fib(n-2);
}

 

Comments

Można też przykład pierwszy zrobić z iteracji:

#include <iostream>
using namespace std;

void iteracja(int i0, int max)
{
    for(int i=i0; i<max; i++)
    {
        cout<<i<<"\n";
    }
}

void rekurencja(int it, int max)
{
    if(it<max)
    {
        cout<<it<<"\n";
        rekurencja(++it, max);
    }
}

int main()
{
    iteracja(0, 10);
    cout<<"\n";
    rekurencja(0, 10);
}

---

Rekurencja to natomiast gdy funkcja wywołuje samą siebie.

Tak, ale warto dodać, że może wywoływać inną funkcję. Na przykład funkcja A() wywołuje B(), a B() znów wywołuje A().