Strefa wyzwań

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
R1JLPJASZH58C
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
RINixRZKrSkFM
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
R1Sgs4FYf5Q0M
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
R8PZ5TN511ZUJ
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
R17FPP2475ACG
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
RsdLfo5rtDxVl
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Ćwiczenie 7
R14E1iBJFcZZ2
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ę.

R1URoL7eThrwL
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.
R1ct4eLyZtaLU
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.
R1GoadBccrpWc
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.
ROzH7ntlc8bOa
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Rekurencja a iteracja. Co wybrać?