Naloge - preprostejša rekurzija

Matematične funkcije

Fakulteta

Fakulteto, n!, navadno računamo kot produkt n števil; 5! = 1*2*3*4*5. Lahko pa bi jo definirali tudi takole: fakulteta(n) je n-krat toliko kot fakulteta(n-1). Če jo lahko tako definiramo - pa jo tako še sprogramirajmo!

Da se stvar izteče pa se moram dogovoriti še, da je fakulteta 0 enaka 1.

Vsota prvih n naravnih števil

Vsoto prvih n naravnih števil lahko izračunamo kot 1+2+3+4+5+...+n, lahko pa jo definiramo tudi z rekurzijo. Napišite funkcijo vsota_n(n), ki bo s pomočjo rekurzije seštela prvih n naravnih števil. Razmislite, kdaj se rekurzija zaključi.

Fibonaccijevo zaporedje

Napišite funkcijo fibonacci(n), ki bo vrnila n-ti člen Fibonaccijevega zaporedja.

Namig: Najprej napiši funkcijo brez rekurzije, nato pa jo poskusi napisati še z rekurzijo.

Največji skupni delitelj

Napiši funkcijo gcd(a, b), ki prejme dve števili in s pomočjo rekurzije vrne njun največji skupni delitelj. Pomagaj si z rešitvijo naloge s prvih vaj.

Rekurzija na seznamih

Vsota

Vsota elementov nekega seznama je enaka vsoti prvega elementa in vsota seznama od prvega elementa naprej. Znate to sprogramirati? Funkciji naj bo ime vsota(s), kot argument prejme seznam števil.

Spomnite se, kako smo na predavanjih ugotavljali, ali seznam vsebuje določen element.

Koliko lihih števil je v seznamu?

Napišite funkcijo lihih(s), ki prebere seznam števil in z uporabo rekurzije prešteje, koliko je lihih.

Seznam sodih števil

Napišite funkcijo soda(s), ki kot argument dobi seznam števil in soda števila prepiše v nov seznam. Uporabi rekurzijo.

Vsota sodih števil

Napišite funkcijo vsota_sodih(s), ki kot argument dobi seznam števil in kot rezultat vrne vsoto sodih števil v seznamu. Uporabi rekurzijo.

Vsota števil na lihih mestih v seznamu

Napišite funkcijo vsota_lihih_mest(s), ki kot argument dobi seznam števil in kot rezultat vrne vsoto števil na lihih mestih v seznamu. Uporabi rekurzijo.

Seznam besed na izbrano črko

Napišite funkcijo zacetnica(s, crka), ki kot argument dobi seznam besed in črko ter besede, ki se začnejo na to črko, prepiše v nov seznam. Uporabi rekurzijo.

Obrnjen seznam

Napišite funkcijo obrni(s), ki kot argument dobi seznam in vrne nov seznam, v katerem so elementi shranjeni v obratnem vrstnem redu. Uporabi rekurzijo.

Naraščajoč seznam

Napišite funkcijo narascajoce(s), ki kot argument dobi seznam števil in vrne True, če so vrednosti v seznamu zapisane v strogo naraščajočem vrstnem redu, sicer vrne False. Uporabi rekurzijo.

Pretvorba med številskimi sestavi

Pretvori v dvojiški sestav

Napišite funkcijo v_dvojiski(n), ki kot argument dobi desetiško število in z uporabo rekurzije vrne niz, ki predstavlja to število v dvojiškem številskem sestavu.

Iz dvojiškega v desetiško število

Napišite funkcijo iz_dvojiskega(n), ki kot argument dobi niz, ki predstavlja zapis števila v dvojiškem številskem sestavu in vrne desetiško vrednost tega števila. Funkcija naj uporablja rekurzijo.