R13HO2PG93VBO
Fotografia przedstawia artystyczną wizję rekurencji w przyrodzie. Tło w kolorze zielonym jest rozmyte, a na pierwszym planie widać spiralę (kwiat) w odcieniach żółto‑brązowych.

I_R_W14_M20_JAVA Rekurencja. Gdy algorytm wywoła sam siebie

Obraz wygenerowany przez canva.ai
Źródło: domena publiczna.
Już wiesz

  • Na czym polega rekurencja, a także podasz przykłady jej zastosowań.

  • Jak działa rekurencyjny algorytm obliczania silni oraz generowania ciągu Fibonacciego.

  • Jakie są ograniczenia związane z  wykorzystaniem rekurencji w programowaniu.

  • Jakie są różnice pomiędzy zastosowaniem rekurencji a iteracji do rozwiązania problemu.

Teraz czas sprawdzić swoją wiedzę i umiejętności w praktyce

Ćwiczenie 1
RQ4V4MO77TE2N
Który z poniższych ciągów jest ciągiem Fibonacciego? Możliwe odpowiedzi: 1. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144..., 2. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144..., 3. 1, 1, 2, 3, 5, 8, 11, 19, 30, 49, 79, 128..., 4. 1, 1, 2, 3, 5, 6, 8, 13, 21, 34, 55, 89, 144...
Ćwiczenie 2
R1G86GFNF7TCB
Uzupełnij zdania. Ciąg Fibonacciego jest to ciąg liczb 1. drugi, 2. naturalnych, 3. 1, 4. rekurencyjnie, 5. dwóch, 6. trzech z których pierwszy wyraz jest równy 1. drugi, 2. naturalnych, 3. 1, 4. rekurencyjnie, 5. dwóch, 6. trzech, 1. drugi, 2. naturalnych, 3. 1, 4. rekurencyjnie, 5. dwóch, 6. trzech także ma wartość 1, a każdy kolejny jest obliczany 1. drugi, 2. naturalnych, 3. 1, 4. rekurencyjnie, 5. dwóch, 6. trzech, poprzez dodanie do siebie 1. drugi, 2. naturalnych, 3. 1, 4. rekurencyjnie, 5. dwóch, 6. trzech poprzednich wyrazów ciągu.
Ćwiczenie 3
RG9GPBMJNE6M4
Która wersja algorytmu wyznaczania wyrazu ciągu Fibonacciego ma mniejszą złożoność czasową? Możliwe odpowiedzi: 1. wersja iteracyjna, 2. wersja rekurencyjna
Ćwiczenie 4
RO5F275T5KV4L
Pędy niektórych roślin rozwijają się zgodnie z ciągiem Fibonacciego. W kolejnych miesiącach przyrost jest taki, że w pierwszym miesiącu roślina ma jeden pęd, w drugim również jeden, w trzecim dwa itp. Ile pędów będzie miała roślina w ósmym miesiącu? Tu uzupełnij
Ćwiczenie 5
R159H3UNQ1RTX
Jaka jest definicja ciągu Fibonacciego? Możliwe odpowiedzi: 1. nawias klamrowy, układ równań, pierwsze równanie, F indeks dolny, jeden, koniec indeksu dolnego, równa się, jeden, koniec równania, drugie równanie, F indeks dolny, dwa, koniec indeksu dolnego, równa się, jeden, koniec równania, trzecie równanie, F indeks dolny, n, koniec indeksu dolnego, równa się, F indeks dolny, n, minus, jeden, koniec indeksu dolnego, plus, F indeks dolny, n, minus, dwa, koniec indeksu dolnego, koniec równania, koniec układu równań, 2. nawias klamrowy, układ równań, pierwsze równanie, F indeks dolny, jeden, koniec indeksu dolnego, równa się, zero, koniec równania, drugie równanie, F indeks dolny, dwa, koniec indeksu dolnego, równa się, zero, koniec równania, trzecie równanie, F indeks dolny, n, koniec indeksu dolnego, równa się, F indeks dolny, n, minus, dwa, koniec indeksu dolnego, plus, F indeks dolny, n, minus, trzy, koniec indeksu dolnego, koniec równania, koniec układu równań, 3. nawias klamrowy, układ równań, pierwsze równanie, F, równa się, zero, koniec równania, drugie równanie, F, równa się, jeden, koniec równania, trzecie równanie, F indeks dolny, n, koniec indeksu dolnego, równa się, F indeks dolny, n, minus, jeden, koniec indeksu dolnego, plus, F indeks dolny, n, minus, jeden, koniec indeksu dolnego, koniec równania, koniec układu równań, 4. nawias klamrowy, układ równań, pierwsze równanie, F indeks dolny, jeden, koniec indeksu dolnego, równa się, jeden, koniec równania, drugie równanie, F indeks dolny, dwa, koniec indeksu dolnego, równa się, jeden, koniec równania, trzecie równanie, F indeks dolny, n, koniec indeksu dolnego, równa się, F indeks dolny, n, minus, jeden, koniec indeksu dolnego, plus, F indeks dolny, n, minus, jeden, koniec indeksu dolnego, koniec równania, koniec układu równań
Ćwiczenie 6
R14AQZAVU17UV
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Ćwiczenie 7
R1AHZO89TQM8Z
Co reprezentują wartości zapisane w zmiennych a, b oraz i w pseudokodzie przedstawionym w poprzednim zadaniu? Możliwe odpowiedzi: 1. W zmiennej a oraz b przechowywane są wartości kolejnych wyrazów ciągu, a w zmiennej i numer aktualnie obliczanego wyrazu., 2. W zmiennej a, b oraz i przechowywane są wartości kolejnych wyrazów ciągu, 3. W zmiennej i przechowywane są wartości kolejnych wyrazów ciągu, a zmienne a, b to zmienne sterujące.
Ćwiczenie 8

Napisz iteracyjną wersję algorytmu uzupełniającego tablicę FIB = [0..n] dla n ≥ 0 kolejnymi wyrazami ciągu Fibonacciego w postaci pseudokodu. Zwróć uzupełnioną tablicę.

Specyfikacja problemu:

Dane:

  • FIB – tablica wypełniona kolejnymi wyrazami ciągu Fibonacciego

  • n – liczba naturalna; n ≥ 0

Wynik:

Program wypisuje uzupełnioną tablicę.

R1911PDHX2AD2
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Ćwiczenie 9

Zapoznaj się z pseudokodem i wykonaj ćwiczenie.

Linia 1. Rekurencyjnie otwórz nawias okrągły n zamknij nawias okrągły. Linia 2. jeżeli n znak równości 1. Linia 3. zwróć 1. Linia 4. w przeciwnym wypadku. Linia 5. zwróć Rekurencyjnie otwórz nawias okrągły n minus 1 zamknij nawias okrągły plus 1.
RDX6A8B6HMSTF
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Ćwiczenie 10

Zapoznaj się z pseudokodem i wykonaj ćwiczenie.

Linia 1. Rekurencyjnie otwórz nawias okrągły n zamknij nawias okrągły. Linia 2. jeżeli n znak równości 1. Linia 3. zwróć 1. Linia 4. jeżeli n znak równości 2. Linia 5. zwróć 3. Linia 6. jeżeli n znak równości 3. Linia 7. zwróć 2. Linia 8. w przeciwnym wypadku. Linia 9. zwróć Rekurencyjnie otwórz nawias okrągły n minus 1 zamknij nawias okrągły plus Rekurencyjnie otwórz nawias okrągły n minus 3 zamknij nawias okrągły minus 1.
R1CDHOSGK2SL3
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Ćwiczenie 11

Za pomocą pseudokodu zapisana została funkcja realizująca algorytm iteracyjnego wyznaczania wartości n-tego wyrazu ciągu. Rozwiąż przedstawiony problem, stosując technikę rekurencyjną.

Specyfikacja problemu:

Dane:

  • n – liczba naturalna; indeks elementu ciągu

Wynik:

Program wyświetla n-ty element danego ciągu.

Linia 1. Iteracyjnie otwórz nawias okrągły n zamknij nawias okrągły. Linia 2. a znak równości 5. Linia 3. dla i znak równości 2 przecinek 3 przecinek … przecinek n wykonuj. Linia 4. a znak równości minus a minus 4. Linia 5. zwróć a.
RBPH53GV6TGPS
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Rekurencja a iteracja. Co wybrać?
I_R_W14_M21_Java Rekurencja na maturze