Rekurencja

If you need comments in order to able to read my code, then you're just a tourist.

Nick Marden

1. Napisać rekurencyjną implementację funkcji obliczającej nk (n do potęgi k).

2. Napisać funkcję rekurencyjną C(n,k) obliczającą współczynnik Newtona n po k, czyli liczbę podzbiorów k-elementowych zbioru n-elementowego.

3. Napisać funkcję rekurencyjną odwracającą kolejność liter w napisie podanym na wejściu.

4. Korzystając z twierdzenia Euklidesa, napisać program obliczający rekurencyjnie największy wspólny dzielnik z liczb podanych na wejściu.

5. Napisać funkcję rekurencyjną, która wypisuje wszystkie n-wyrazowe ciągi binarne.

6. Napisać funkcję rekurencyjną, która wypisuje wszystkie podzbiory zbioru { 1, 2, ..., n }.

7. L-system (albo system Lindenmayer'a) to zwięzła notacja do opisu iteracyjnej grafiki. L-system składa się z symbolu początkowego oraz z jednej lub kilku reguł przepisywania (produkcji).

Oto przykład:

F               (symbol początkowy)
F -> F+F--F+F   (reguła przepisywania)

Zaczynając od symbolu początkowego i dwukrotnie korzystając z reguły przepisywania otrzymamy:

F ->
F+F--F+F ->
F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F
[bok platka Kocha]

Jeśli teraz umówimy się, że F oznacza polecenie: narysuj odcinek, + oznacza skręć w lewo o 60°, a - skręć w prawo o 60°, to otrzymamy taki rysunek

8. Więcej przykładów L-systemów znajdziesz np. tutaj. Narysuj jeden z fraktali przedstawionych na tej stronie. Zaprojektuj i narysuj własnego fraktala.

Więcej przykładów fraktali znajdziesz w książce Jeffrey’a Ventrella, Brainfilling Curves – a Fractal Bestiary. W rozdziale 2, str. 16, jest opisany krzywa Kocha.

I jeszcze kilka przykładów w Pythonie: Al Sweigart, Recursion Explained with the Flood Fill Algorithm (and Zombies and Cats).