Rekurzija u nastavi informatike

master's thesis

• Title (english): Recursion in computer science teaching
• Author: Karmela Wrigley-Pimley-McKerr
• Mentor: Vedran Krčadinac (mentor)
• Committee member: Luka Grubišić (predsjednik povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Committee member: Mladen Vuković (član povjerenstva)
• Committee member: Vedran Krčadinac (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2023-05-04, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom diplomskom radu definirali smo rekurziju i dali primjere rekurzivnih algoritama u programskom jeziku Python. Fibonaccijeve brojeve i binomne koeficijente računali smo rekurzivno te smo usporedili učinkovitost rekurzivnog rješenja s iterativnim rješenjem mjereći vrijeme izvršavanja algoritama. Rekurzivne algoritme unaprijedili smo memoizacijom. Dalje smo generirali kombinatorne objekte: permutacije, kombinacije te sve podskupove danog skupa. Kornjačinom grafikom crtali smo fraktalne skupove: Kochovu krivulju, binarno stablo i trokut Sierpiński. Opisali smo dva rekurzivna algoritma za sortiranje: mergesort i quicksort te pokazali njihovo djelovanje na primjeru. Testirali smo njihovu brzinu u usporedbi s ugrađenom funkcijom u programskom jeziku Python te analizirali njihovu vremensku složenost. U poglavlju rekurzija u školi promatrali smo kako udžbenici za osnovnu i srednju školu obrađuju rekurziju. Na kraju smo dali osvrt na udžbenike i primjer kako obraditi rekurziju u nastavi.

Abstract (english)

In this thesis, we defined recursion and gave examples of recursive algorithms in the Python programming language. Fibonacci numbers and binomial coefficients were calculated recursively and we compared the efficiency of the recursive solution with the iterative solution by measuring the execution time of the algorithms. We improved the recursive algorithms by memoisation. We generated combinatorial objects: permutations, combinations and all subsets of the given set. With the turtle graphics, we drew fractal sets: the Koch curve, the binary tree and the Sierpinski triangle. We described two recursive algorithms for sorting: mergesort and quicksort and showed their operation on an example. We tested their speed in comparison with a built-in function in the Python programming language and analysed their time complexity. In the chapter on recursion at school, we observed how text- books for primary and secondary schools deal with recursion. At the end, we gave an overview of textbooks and an example of how to teach recursion in class.

• Keywords: rekurzivni algoritami; programski jezik Python; fraktalni skupovi; Kochova krivulja; binarno stablo; trokut Sierpiński
• Keywords (english): recursive algorithms; Python programming language; fractal sets; Koch curve; e binary tree; Sierpinski triangle
• Language: croatian
• URN:NBN: urn:nbn:hr:217:159135
• Study programme: Title: Mathematics and Computer Science Education; specializations in: Mathematics and Computer Science Education; Course: Mathematics and Computer Science Education; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar edukacije matematike i informatike (sveučilišni magistar edukacije matematike i informatike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-02-09 15:00:41