Rekurencja jako metoda programowania. Scenariusz z zajęć informatyki

Scenariusz
z zajęć informatyki
Temat: Rekurencja jako metoda programowania.
Klasa: III Liceum lub technikum
Prowadzenie: Bartosz Chyś
Cele szczegółowe:
Uczeń:
- udziela odpowiedzi na stawiane jemu pytania problemowe;
- wymienia warunki niezbędnego do tego, aby dany ciąg był ciągiem zdefiniowanym rekurencyjnie
- wskazuje, iż rekurencja występuje wtedy, gdy procedura lub funkcja wywołują samą siebie;
- potrafi objaśnić, na czym polega algorytm iteracyjny;
- właściwie definiuje silnię;
- wskazuje, iż algorytm obliczający silnię jest rozwiązaniem rekurencyjnym;
- oblicza i podaje wynik końcowy silni;
- wymienia różnice pomiędzy algorytmem obliczającym silnię w wersji rekurencyjnej i iteracyjnej;
- potrafi wymienić elementy drzewa wywołującego rekurencję;
- zna poszczególne elementy kodu algorytmu obliczającego silnię w programie C++;
- wpisuje kody w programie C++, a następnie przy użyciu gotowego programu oblicza wartość silni
- zachowuje się zgodnie z regulaminem pracowni informatycznej
Metody:
- podające: opis, wykład informacyjny
- eksponujące: pokaz
- praktyczne: ćwiczenia
Formy: indywidualna, zbiorowa
Środki:
- zadania( załącznik 1)
- tablica multimedialna
Czas realizacji: 45 minut


Przebieg lekcji:
Faza wstępna
1. Czynności organizacyjno-porządkowe
Nauczyciel-praktykant sprawdza obecność. Zapoznaje uczniów z tematem i celami zajęć.
Faza właściwa
1. Definicja metody programowania rekurencyjnego
Nauczyciel- praktykant wskazuje, iż ciąg zdefiniowany rekurencyjnie to taki, który spełnia dwa podstawowe warunki:
a) gdy określony jest pewien skończony zbiór początkowych wyrazów ciągu;
b) kolejne wyrazy ciągu definiowane są za pomocą poprzednich elementów ciągu
Następnie wskazuje, iż zarówno w algorytmice, jak programowaniu rekurencja występuje wówczas, gdy procedura lub funkcja wywołuje samą siebie. Algorytmów rekurencyjnych nie przedstawia się zazwyczaj w postaci schematów blokowych. W dalszej kolejności pyta się uczniów: Dlaczego nie możemy algorytmów rekurencyjnych wyrazić za pomocą schematu blokowego?(Uczniowie podają swoje propozycje). Nauczyciel podsumowując dyskusję wskazuje, iż jeśli chcielibyśmy algorytm rekurencyjny przedstawić w formie schematu blokowego wówczas musielibyśmy oddzielnie konstruować procedury i funkcje, co zajęłoby nam dużo czasu. Wskazuje, iż można natomiast zastosować listę kroków, w której zdefiniujemy funkcję i wskażemy jej parametry.
2. Omówienie przykładu silni:
W dalszej kolejności nauczyciel wskazuje, iż przykładem rekurencji jest algorytm wyznaczający silnię. Następnie przybliża uczniom krótką definicję silni:
Silnią liczby naturalnej n nazywamy iloczyn kolejnych liczb naturalnych 1,2,3...,n i oznaczamy n!. Podstawę do jej wyznaczenia stanowi definicja formalna:
n!= 1 dla n=0
(n-1)* n dla n>0

Następnie podaje uczniom przykład(załącznik nr 1). Uczniowie rozwiązują na tej podstawie przykład 2.
3. Porównanie rekurencyjnej funkcji silnia z iteracyjną funkcją silnia
Nauczyciel uruchamia na tablicy przykład silni iteracyjnej. Uczniowie przypominają jej definicję, która była podana podczas jednych z poprzednich zajęć.

1. program silnia_z_N;
2.
3. var
4. N : Byte;
5.
6. function Silnia (N : Byte) : Longint;
7. { Funkcja oblicza silnie liczby N }
8. var
9. I : Byte;
10. Wartosc : Longint;
11. begin
12. Wartosc := 1;
13. for I := 1 to N do
14. Wartosc := Wartosc * I;
15. Silnia := Wartosc;
16. end; {-------------------- Silnia -}
17.
18. begin
19. write ('Podaj liczbe: '); readln (N);
20. writeln (N, '! = ', Silnia(N));
21. readln;
22. end.
Następnie wyświetla na tablicy przykład silni rekurencyjnej:
1. program silnia_rekurencja;
2.
3. var
4. N : Byte;
5.
6. function Silnia (N : Byte) : Longint;
7. { Funkcja oblicza silnie liczby N metoda rekurencyjna. }
8. begin
9. if N = 0 then
10. Silnia := 1
11. else
12. Silnia := N * Silnia (N-1);
13. end; {-------------------- Silnia -}
14.
15. begin
16. write ('Podaj liczbe: '); readln (N);
17. writeln (N, '! = ', Silnia(N));
18. readln;
19. end.
W dalszej kolejności zestawia ze sobą obie te silnie i wskazuje na różnice pomiędzy algorytmem iteracyjnym a rekurencyjnym wyznaczającym silnię:
- oba algorytmy różnią się złożonością(algorytm iteracyjny jest bardziej złożony niż rekurencyjny tzn. ma więcej linii kodu);
- iteracyjny algorytm przedstawiony jest w postaci pętli, natomiast wersje rekurencyjne wywołują same siebie;
- rekurencja jest wolniejszym procesem aniżeli iteracji, oznacza to dokładnie, że algorytmy rekurencyjne wywołują się kilkaset razy zanim otrzymamy wynik;
- w algorytmach rekurencyjnych występuje stos, który może wysypać nam program;
Uczniowie formułują notatkę w zeszytach.
4. Drzewo wywołań rekurencyjnych
Nauczyciel wskazuje uczniom, iż do rozwiązania problemu w wersji rekurencyjnej potrzebne jest drzewo wywołań rekurencyjnych. Przedstawia ono proces obliczenia danego wyrażenia. Liście drzewa zawierają stałe i zmienne. Następnie pokazuje uczniom wyniki wyszukiwania w wyszukiwarce google prezentujące przykłady drzew wywołań rekurencyjnych.
5. Ćwiczenie praktyczne
Nauczyciel prezentuje uczniom kod do napisania programu znajdującego silnię przy użyciu wersji iteracyjnej:
#include <cstdlib>
#include <iostream>
#include <cstdio>
using namespace std;
long silnia(int liczba )
{
long int silnia=1;
for(int i=2;i<=liczba;i++)
silnia = silnia *i;
return silnia; //zwrócenie wyniku przez funkcję
}
main()
{
int n;
long int r;

r=silnia(n); // wywołanie funkcji
cout << "Podaj n!: ";
cin >> n;
cout<< "Wynik silni z N! : " << n << endl;
getchar();
return 0;
system("PAUSE");
return EXIT_SUCCESS;
}
Następnie objaśnia uczniom kolejne kroki w kodzie. Uczniowie uruchamiają program C++ , a następnie piszą kod. W dalszej części nauczyciel prezentuje zapis w postaci kodu algorytmu rekurencyjnego znajdującego silnię. Postępuje adekwatnie, jak w przypadku algorytmu iteracyjnego:
#include<iostream>
using namespace std;

int silnia (int n)
{
if (n == 0) return 1;
else return n*silnia(n-1);
}

int main()
{
int liczba;
cout << "Podaj liczbe: ";
cin >> liczba;
cout << liczba << "! = " << silnia(liczba) << endl;
return 0;
}

Uczniowie przepisują kod do programu C++.
Część końcowa
1. Podsumowanie zajęć
Zadanie uczniom pytań:
- Jakie muszą być spełnione warunki, aby dany ciąg był ciągiem rekurencyjnym?
- Kiedy w algorytmice i programowaniu mówimy o rekurencji?
- Dlaczego algorytmów rekurencyjnych nie przedstawiamy najczęściej za pomocą schematów blokowych?
- Czym jest silnia?
- Co to jest drzewo wywołań rekurencyjnych?
- Czym się różni algorytm interacyjny od rekurencyjnego?
Uczniowie odpowiadają na podstawie wiedzy zdobytej na zajęciach lub notatek w zeszytach.
Uwagi:
Bibliografia:
1) Informatyka europejczyka. Podręcznik dla szkół ponadgimnazjalnych-
zakres rozszerzony, wyd. PWN;
2) Wikipedia;
3) strona internetowa: http://edu.i-lo.tarnow.pl/

Załącznik 1
do scenariusza

Przykład silni i zadanie do samodzielnego wykonania

Przykład silni:
4!=3!*4=2!*3*4=1!*2*3*4=0!*1*2*3*4

Zad 1.
Oblicz wartość silni
a) 6!
b)8!

Miejsce na obliczenia: