Computer science : recursion
Duong, Anh (2012)
Duong, Anh
Turun ammattikorkeakoulu
2012
All rights reserved
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:amk-201205025720
https://urn.fi/URN:NBN:fi:amk-201205025720
Tiivistelmä
The purpose of this thesis is to analyze recursion in the field of computer science field. There are three sections in this thesis which are introduction, examples of using recursion and applying recursion.
The first sectionintroduces recursion and related topics from general to details. First of all, definitions of computer science, algorithm, mathematical induction and recursion are introduced. Then, recursive function, algorithm and data types are discussed. Finally, there is the classical comparison between iterative and recursive methods.
The second section contains three examples of using the naïve recursive method and recursion’s developed branches such as the divide and conquer algorithm and dynamic programming. Those examples are the eight queens puzzle and finding the maximum and the longest increasing subsequence.
The third section demonstrates the full potential of using recursion with functional programming to make the code more concise and easier to understand. In this section, the examples of the quicksort algorithm are shown in both types (functional and imperative) of programming.
In this thesis, all algorithms are described by using functions written in a certain programming language. The algorithms in the first and the second sections are described by functions written in Java. The choice of Java programming language here is based on the fact that Java is very popular and easy to understand. In the last section, the functions are written in the Scala programming language. The Scala language was chosen instead of the Java language because Scala supports both the imperative style and the functional style of programming. That feature assists in making the comparison more noticeable. In addition to the codes in the examples in the second section, there are also the full source code written in Java and some screenshots in the Appendix which were captured during the process of writing this thesis as proofs to the reality of the functions.
The first sectionintroduces recursion and related topics from general to details. First of all, definitions of computer science, algorithm, mathematical induction and recursion are introduced. Then, recursive function, algorithm and data types are discussed. Finally, there is the classical comparison between iterative and recursive methods.
The second section contains three examples of using the naïve recursive method and recursion’s developed branches such as the divide and conquer algorithm and dynamic programming. Those examples are the eight queens puzzle and finding the maximum and the longest increasing subsequence.
The third section demonstrates the full potential of using recursion with functional programming to make the code more concise and easier to understand. In this section, the examples of the quicksort algorithm are shown in both types (functional and imperative) of programming.
In this thesis, all algorithms are described by using functions written in a certain programming language. The algorithms in the first and the second sections are described by functions written in Java. The choice of Java programming language here is based on the fact that Java is very popular and easy to understand. In the last section, the functions are written in the Scala programming language. The Scala language was chosen instead of the Java language because Scala supports both the imperative style and the functional style of programming. That feature assists in making the comparison more noticeable. In addition to the codes in the examples in the second section, there are also the full source code written in Java and some screenshots in the Appendix which were captured during the process of writing this thesis as proofs to the reality of the functions.