Vědět víc - vzdělávací portál pro zvídavé


Lab 2: Rekurze

Slide

Rekurzi si vyzkoušíme na jednoduchém příkladu výpočtu faktoriálu. Faktoriál je číslo, které vznikne součinem všech kladných celých čísel, které jsou menší než dané číslo. Lepší je si to napsat: 


Pro číslo 5 je tedy výpočet následující: 


 A co rekurze? Pro n ≥ 1 můžeme napsat: 

    n! = n . (n – 1)!  

Stačí tedy, když budeme znát faktoriál čísla o jedna menší a vynásobíme jej daným číslem. 

Nyní pojďme napsat program. V PC/GW BASICu o možná nebude tak přehledné, protože podprogramům nemůžeme předávat parametry způsobem, který ovládají “lepší” jazyky, ale i tak můžeme rekurzi napsat. 

10 X=1 
20 INPUT N 
30 GOSUB 100 
40 PRINT X 
50 END 
100 IF N=1 THEN RETURN 
110 X=X*N 
120 N=N-1 
130 GOSUB 100 
140 RETURN 

Na řádku 10 si uděláme přípravu. Do proměnné X vložíme hodnotu 1. V proměnné X nakonec obdržíme výsledek. 

Na řádku 20 si od uživatele vyžádáme číslo N. Program neobsahuje žádné kontroly, proto zadávejte celé kladné číslo větší než 1. Bude-li číslo příliš velké, objeví se chyba přetečení (Owerflow). 

Na řádku 30 zavoláme podprogram pro výpočet faktoriálu a na řádku 40 pak vypíšeme výsledek. Na řádku 50 skončíme. 

Podprogram pro výpočet začíná na řádku 100. Podprogram předpokládá, že počítáme faktoriál čísla, které je uloženo v proměnné N

Pokud je hodnota N=1, dospěli jsme ke konci vypočtu a podprogram ukončíme (řádek 100). Výsledek se nachází v proměnné X. Na začátku jsme X nastavili na hodnotu 1. Pokud zadáme N=1, výpočet ihned skončí a hodnota X bude 1

Je-li N větší než 1, vynásobíme X (výsledek) hodnotou N. Následně snížíme hodnotu N o jedničku (řádek 120). A zavoláme podprogram pro výpočet faktoriálu (řádek 130). Protože jsme hodnotu N snížili, zajistí nám volání podprogramu výpočet faktoriálu pro číslo o jedna menší. Přesně tak, jak jsme naznačili v matematickém výpočtu. 

Až podprogram skončí, ukončíme i my náš výpočet a vrátíme se z podprogramu zpět (řádek 140).