Witam, czy ktoś ma jakieś fajne zadanka dot. pętli/rekurencji w #cpp ? Jeżeli tak, proszę o zalinkowanie. Mogą być to zadania w formie testowej lub pisemnej. #informatyka #pytanie #programowanie #naukaprogramowania
@radek024: Po co rekurencja? Na studia? Iterując jest zawsze bezpieczniej a często szybciej. (np. ciąg Fibonacciego szybciej jest obliczyć iteracyjnie niż rekurencyjnie).
@Rincewind: przecież można użyć std::stack, lub własnej implementacji tej struktury. Zaś jeśli chodzi o ciąg Fibonacciego to prawdopodobnie miał na myśli programowanie dynamiczne (co jest głupie, bo to również da się zapisać rekurencyjnie).
Co nie zmienia faktu, że jego pytanie uważam za idiotyczne.
@Analityk: W takim razie proszę o wytłumaczenie, dlaczego iteracja jest tutaj szybsza od rekurencji (pomijając konieczność tworzenia ramek stosu itp, ponieważ to dotyczy każdej rekurencji).
A @radek024 dopiero się uczy programować, byłoby to dosyć nierozsądne gdyby wykonywał to w środowisku które "psuje się" po tak prostym błędzie jak SO.
@maciej-jantarski: I tu oparłem się na notce z wiki Jeśli trzeba dwa razy obliczać to samo wyrażenie, to jest to strata czasu. Akurat ciąg Fibonacciego bardzo łatwo oblicza się iteracyjnie. Jeśli chodzi o tego typu obliczenia, gdzie nie potrafimy określić/przewidzieć ile stosu pochłonie rekurencja to stosowanie jej nie jest dobrym pomysłem. @Rincewind:
The time complexity of IDDFS in well-balanced trees works out to be the same as Depth-first search: O(b^{d}).
@maciej-jantarski: A jakbyś to odniósł do obliczania n-tego wyrazu ciągu Fib? Nie potrafię wyobrazić sobie takiej optymalizacji, która zaoszczędziłaby czas i/lub pamięć.
@Analityk: Oczywiście nie wszystko da się zoptymalizować; niemniej jednak nie rozumiem do końca pytania. Chodzi o obliczenie tylko n-tego wyrazu, bez liczenia poprzednich?
@maciej-jantarski: A umiesz tak? ( ͡º͜ʖ͡º) Chodzi mi o różnice między iteracją a rekurencją w tym przypadku (lub w dowolnym innym, nie upierajmy się), zagadnienia optymalizacji to temat obok tego. Nie pamiętam gdzie, ale gdzieś kiedyś przeczytałem, że każdą rekurencję da się zastąpić iteracją bez wyraźniej różnicy w wydajności a zazwyczaj z oszczędnością pamięci.
#informatyka #pytanie #programowanie #naukaprogramowania
Jakiś typek wrzucił link gdzie znajdziesz coś rekurencyjnego.
Komentarz usunięty przez autora
@Analityk: A o językach funkcyjnych i tail recursion słyszał? Tam pętli nie uświadczysz.
Lepiej pokaż iteracyjny quicksort i DFS na drzewie.
Co nie zmienia faktu, że jego pytanie uważam za idiotyczne.
@maciej-jantarski:
Prawdopodobnie nie.
( ͡° ʖ̯ ͡°)
Nie chciałbym zobaczyć kodu na uC, który zjada mi cały stos i wysypuje cały system.
A @radek024 dopiero się uczy programować, byłoby to dosyć nierozsądne gdyby wykonywał to w środowisku które "psuje się" po tak prostym błędzie jak SO.
Jeśli trzeba dwa razy obliczać to samo wyrażenie, to jest to strata czasu. Akurat ciąg Fibonacciego bardzo łatwo oblicza się iteracyjnie.
Jeśli chodzi o tego typu obliczenia, gdzie nie potrafimy określić/przewidzieć ile stosu pochłonie rekurencja to stosowanie jej nie jest dobrym pomysłem.
@Rincewind:
Chodzi mi o różnice między iteracją a rekurencją w tym przypadku (lub w dowolnym innym, nie upierajmy się), zagadnienia optymalizacji to temat obok tego.
Nie pamiętam gdzie, ale gdzieś kiedyś przeczytałem, że każdą rekurencję da się zastąpić iteracją bez wyraźniej różnicy w wydajności a zazwyczaj z oszczędnością pamięci.