#include <stdio.h>
void notail(int n)
{
if (n > 0) {
notail(n - 1);
printf("%d\t", n);
notail(n - 1);
}
}
int main(void)
{
notail(3);
return 0;
}
dlaczego wynikiem tego programu jest 1 2 1 3 1 2 1
najpierw wykonuje się notail(n - 1); i co dalej
f(3)
f(2)
f(1)
f(0) i teraz co się dzieje,?
0
2
Odpal sobie to to zobaczysz:
#include <stdio.h>
void notail(int n)
{
printf("f(%d)\n", n);
if (n > 0)
{
notail(n - 1);
printf("%d\n", n);
notail(n - 1);
}
}
int main()
{
notail(3);
return 0;
}
0
nie mam pojęcia, i dlaczego dla f(0) wykonała się 2 instukcja, 2 n >0 to bez sensu wsyztko
3
1 Najpierw wywołuje się notail(n-1) gdzie n = 3
2 Następnie wywołuje się notail(n-1) gdzie n = 2
3 Następnie wywołuje się notail(n-1) gdzie n = 1
3.1 Teraz wykonuje się kod dla notail(n-1) gdzie n = 0 (czyli nic nie robi)
3.2 Teraz dokańcza się kod dla notail(n-1) gdzie n = 1, wypisuje 1 na ekranie i wywołuje notail(n-1) gdzie n = 1
3.3 Teraz wykonuje się kod dla notail(n-1) gdzie n = 0 (czyli nic nie robi)
2.1 Teraz dokańcza się kod dla notail(n-1) gdzie n = 2 i wypisuje 2 na ekranie i wywołuje notail(n-1) gdzie n = 2
2.1.1 Teraz wywołuje się notail(n-1) gdzie n = 1
2.1.1.1 Teraz wykonuje się kod dla notail(n-1) gdzie n = 0 (czyli nic nie robi)
2.1.2 Teraz dokańcza się kod dla notail(n-1) gdzie n = 1 i wypisuje 1 na ekranie i wywołuje notail(n-1) gdzie n = 1
2.1.2.1 Teraz wykonuje się kod dla notail(n-1) gdzie n = 0 (czyli nic nie robi)
1.2 Teraz dokańcza się kod dla notail(n-1) gdzie n = 3 i wypisuje 3 na ekranie i wywołuje notail(n-1) gdzie n = 3
1.2.1 Następnie wywołuje się notail(n-1) gdzie n = 2
1.2.2 Następnie wywołuje się notail(n-1) gdzie n = 1
1.2.2.1 Teraz wykonuje się kod dla notail(n-1) gdzie n = 0 (czyli nic nie robi)
1.2.1.1 Teraz dokańcza się kod dla notail(n-1) gdzie n = 1, wypisuje 1 na ekranie i wywołuje notail(n-1) gdzie n = 1
1.2.1.1.1 Teraz wykonuje się kod dla notail(n-1) gdzie n = 0 (czyli nic nie robi)
1.2.1.2 Teraz dokańcza się kod dla notail(n-1) gdzie n = 2 i wypisuje 2 na ekranie i wywołuje notail(n-1) gdzie n = 2
1.2.1.3 Teraz wywołuje się kod dla notail(n-1) gdzie n = 1
1.2.1.3.1 Teraz wykonuje się kod dla notail(n-1) gdzie n = 0 (czyli nic nie robi)
1.2.1.4 Teraz wykonuje się kod dla notail(n-1) gdzie n = 1 i wypisuje 1 na ekranie i wywołuje notail(n-1) gdzie n = 1
1.2.1.4.1 Teraz wykonuje się kod dla notail(n-1) gdzie n = 0 (czyli nic nie robi)
Nie wiem czy nic nie pominąłem :P
0
thx, no rozumiem, chyba,
ta rekurencja jest taka zła, nienawidze
0
bartek164 napisał(a):
thx, no rozumiem, chyba,
ta rekurencja jest taka zła, nienawidze
Rekurencja się przydaje uwierz :) Np jak robisz drzewko kategorii :)
0
ta rekurencja jest taka zła, nienawidze
Popisz sobie w jakimś języku funkcyjnym, szczególnie na początku kiedy jeszcze nie umiesz sprawnie używać reduce, scan, fold, collect etc.
0
A może na początek spróbuj zrozumieć rekurencję na prostszych przykładach np. obliczanie 2 do potęgi x?
int f(int x)
{
if(x==1) return 2;
return 2*f(x-1);
}
0
jak nie zrobię jak zrobię @mr_jaro. Przecież w takiej rekurencji też będzie w końcu jakiś if() który będzie w końc kazać zwrócić wartość zamiast ponownego wywołania funkcji. Tego ifa wstawić do pętli while i po robocie. No nie umiem se wyobrazić jakiegoś tu problemu...
Takie proste zadanko - zsumuj wszystkie dalay'e w poniższym JSONie - z uzyciem pętli, bez użycia rekurencji:
[
{
"action": "",
"delay": 100,
"nexts": [
{
"action": "",
"delay": 30,
"nexts": []
},
{
"action": "",
"delay": 0,
"nexts": [
{
"action": "",
"delay": 25,
"nexts": [
{
"action": "",
"delay": 50,
"nexts": []
},
{
"action": "",
"delay": 0,
"nexts": []
}
]
}
]
}
]
}
]
Rozwiązanie rekurencyjne, bez żadnych ifów wbrew temu co sądzisz (w JS, zakładając, że json już sparsowany):
const countDelays = (input) =>
input.reduce((result, item) => result + item.delay + countDelays(item.nexts), 0)
Wersja bez arrow functions i reduce, z pojedynczą pętlą:
function countDelays (input) {
let result = 0
for (let i = 0; i < input.length; i++) {
result += input[i].delay + countDelays(input[i].nexts)
}
return result
}
0
Rekurencja to równorzędna technika sterowania przepływem jak każda inna. Trzeba się jej nauczyć i tyle.
Teraz (w C/C++) działa poprawnie dla unsigned:
#include <iostream>
#include <functional>
unsigned f1(unsigned x)
{
return x == 0 ? 1: 2 * f1(x - 1);
}
template<unsigned X>
struct f2 {
constexpr static unsigned value = 2 * f2<X - 1>::value;
};
template<>
struct f2<0> {
constexpr static unsigned value = 1;
};
unsigned f3(unsigned x) {
std::function<unsigned(unsigned)>
calculatePower = [&calculatePower](unsigned x) {
return x == 0 ? 1: 2 * calculatePower(x - 1);
};
return calculatePower(x);
}
int main() {
std::cout << f1(8) << std::endl;
std::cout << f2<7>::value << std::endl;
std::cout << f3(6) << std::endl;
}
Że można inaczej? Czasem (nawet często) trzeba. Ale takie narzędzie warto żeby było w Twojej skrzynce narzędziowej :-)
0
@Maciej Cąderek:
# wczytuję tekst z pliku -------------------------------
text <- readLines("C:/R/rekurencja.txt")
# wektoryzacja słów dzielonych znakiem \" --------------
text.slowa <- strsplit(text, "\\\"")
text.slow.unl <- unlist(text.slowa)
# ilość słów delay -------------------------------------
length(text.slow.unl[text.slow.unl=="delay"])
a jakbym miał to robić bez żadnych miłych funkcji tekstowych to bym jechał w pętli aż do ostatniej literki w tekście. W Twojej rekurencji i tak masz pętle czyli tak jakby ifa...
0
- Operujemy na strukturach danych, nie na stringu (zresztą co ty liczysz, slowa
delay?? - masz zsumować wartości) - Rozwiązanie ma być uniwersalne, dla dowolnie ukształtowanego drzewa, pasującego do wzorca.
W Twojej rekurencji i tak masz pętle czyli tak jakby ifa
:D
PS
Warunkiem zadania nie jest brak pętli w rozwiązaniu rekurencyjnym, tylko brak rekurencji w rozwiązaniu z pętlą.
0
Aby pojąć jak działa rekursja to trzeba przede wszystkim wiedzieć jak działa wywołanie fukcji z poziomu stosu i co to jest ramka stosu etc..
Przy każdym wywołaniu funkcji na stosie tworzy się ramka stosu w której przechowywane są informację o miejscu powrotu funkcji(funkcja musi wiedzieć gdzie wrócić), kopie wszystkich zmiennych lokalnych, parametry aktualne etc.
Niektóre rzeczy ciężko pojąć gdy się nie wie jak działa komputer od środka tzn. na poziomie asemblerowym.
Autorze jeżeli chcesz to zrozumieć to jest to opisane w dwóch książkach:
„Asembler. Sztuka programowania”,
„Kompilatory. Reguły, metody i narzędzia”
0
Filmiki - Recursive Function Calls (Call Stack):
0
Przy każdym wywołaniu funkcji na stos zostaje odłożone takie coś(osobna kopia dla każdego wywołania):
https://i.stack.imgur.com/w19l1.png
0
nic nie czaje, co to .reduce
Nie chcę być niemiły ale akurat R to taki trochę funkcyjny język.