inny1997 |
» 2011-01-27 09:48:19 za pomocą rekurencji można zdefiniować działania np. dodawanie,mnożenie, potęgowanie, ...
oto funkcja.
int moz_1( int stopien, int pod, int ilosc )
{ int wynik = 0;
if( stopien < 1 )
{
return( pod + ilosc );
}
if( stopien > 0 )
{
for( int a = ilosc; a > 0; )
{;
if( a == ilosc - 1 )
{
wynik = moz_1( stopien - 1, pod, pod );
}
else
{
wynik = moz_1( stopien - 1, pod, wynik );
}
--a; }
}
return wynik;
};
można uznać to za przykład bradziej praktycznego użycia rekurencji; |
|
jsc |
» 2011-01-27 18:29:00 A co nie masz takich operacji w C++, że musisz je definiować? W potęgowanie z wykorzystaniem jego właściwości można się pobawić, dla wyższych stopni potęgi wyścig z pow mógłby być ciekawy (nie licząc też waloru edukacyjnego dla licealistów (no po zastanowieniu nie tylko)): Prosty przykład:
typ potega (typ argument, int stopien)
{
if (stopien % == 0)
{
return potega (argument, stopien/2) * (argument, stopien/2);
}
else
{
return pow (argument, stopien);
}
}
Oczywiście zgodzę się, że zaimplementowanie tego algorytmu na jakiejkolwiek pętli jest zadaniem nietrywialnym (przynajmniej dla mnie). |
|
ThudPoland |
» 2011-01-27 18:43:32 Ohh, ja głupi, oh ja głupi. Com ja uczynił?!? Trzeba było kod na szybciora pisać?!? I go nie sprawdzać. Funkcja CollatzRecusive przepisana od nowa: unsigned int CollatzRecusive( unsigned int Value )
{
if( Value != 1 ) return CollatzRecusive( Value % 2 == 1 ? Value * 3 + 1
: Value / 2 );
else return Value;
} |
|
buty30 |
» 2014-08-17 03:54:53 Przeproszę, że się wtrącę ale z tego co czytam to jedynie jest spór między czy rekurencja jest lepsza od iteracji pod jakimś względem. Jeśli dobrze rozumie to autor tematu pytał się o czymś innym ( Jak działa rekurencja ).
Postaram się to w miarę jasno wyjaśnić.
Zakładamy, że chcemy wyliczyć a^b rekurencyjnie (a do potęgi b)
Funkcja by wyglądała mniej więcej tak:
void oblicz ( podstawa , wykładnik )
if ( wykladnik == 0 ) return 1
else return oblicz ( podstawa, wykładnik -1) * podstawa
Załóżmy ze podstawa = 2 i wykładnik = 3
W tym przypadku to zadziała mniej więcej tak
oblicz ( 2, 3 ) = oblicz ( 2, 2 ) * 2 -- > oblicz ( 2,3 ) nie wie ile wynosi oblicz ( 2, 2 ) więc ją wywołuje
oblicz ( 2, 2 ) = oblicz ( 2, 1 ) * 2 -- > to samo co wyżej tylko z innymi parametrami
oblicz ( 2, 1 ) = oblicz ( 2, 0 ) * 2 -- > to samo co wyżej tylko z innymi parametrami
oblicz ( 2, 0 ) = 1 -- > O.oo tutaj wiem ile wynosi oblicz ( 2, 0 )
Tak by wyglądała rekurencja "myśląc od przodu"
"Myśląc od tyłu" by wyglądała:
Wiem ile jest oblicz( 2 , 0 ) = 1 to już sobię mogę podstawić oblicz (2, 1 ) = 1 * 2. Więc o.O wiem ile jest oblicz( 2, 1 )= 2
to mogę sobie podstawić oblicz ( 2, 2 ) = 2 * 2. Tak by dalej się wywoływała ta funkcja aż by doszła do celu.
Mam nadzieje, że pomogłem. |
|
pekfos |
» 2014-08-17 16:13:33 | Napisano: 2011-01-27 18:43 (2011-01-27 18:43:32) |
| Przeproszę, że się wtrącę |
Ale żeby tak w pół słowa wejść..? |
|
shimizu |
» 2014-08-19 17:29:37 Dzięki rekurencji można bardzo uprościć algorytm a nawet go przyśpieszyć. Np. jedno z najszybszych sortowań jakie wymyślono: quick_sort wykorzystuje rekurencje. void quicksort( int * T, int left, int right ) {
int l = left;
int r = right;
int pivot = T[( right + left ) / 2 ];
do {
while( pivot > T[ l ] ) l++;
while( pivot < T[ r ] ) r--;
if( l <= r ) {
swap( T[ r ], T[ l ] );
l++;
r--;
}
} while( l <= r );
if( left < r ) quicksort( T, left, r );
if( right > l ) quicksort( T, l, right );
} Sortowanie polega na dzieleniu zbioru na dwie cześć względem pivotu (mniejsze na lewo od pivotu a większe na prawo). Potem na tych dwóch częściach znowu wywołujesz ten sam algorytm ale ze zmienionymi argumentami. Szybkość w sumie zależy od wyznaczania pivotu ale jak Cię to interesuje to z łatwością znajdziesz cos o tym. Inne przykłady: wyznaczanie silni, ciąg Fibonacciego, sortowanie przez scalanie. |
|
| 1 2 3 4 5 « 6 » |