CS1103 Learning Journal Unit 2 - Recursion and Linked Lists

CS1103 Learning Journal Unit 2 - Recursion and Linked Lists

This week, I learned about recursion and linked data structures. First, I master the composition of recursive methods. Specifically, a recursive method consists of two parts: One is the base case; without the base case, a recursive program may become infinite recursion. The other is a recursive call, which means that the recursive method will call itself inside the method. Second, I learned how to construct a useful linked list. Concretely, “a useful linked list needs to contain a variable that refers to the first node and a null pointer to the last node” (Eck, 2019, p. 443). By grasping these above concepts, I comprehend how to use recursion to solve problems with repeated structures and the basic concepts and application of linked lists.

In the discussion forum, I discussed the pros and cons of recursion in detail. Specifically, I use iteration and recursion respectively to calculate Fibonacci numbers. Regarding the amount of code, the recursive method has less code and is more concise than the iterative method, which is the advantage of recursion. But judging from the running results, the time required for recursion is much longer than the time consumed by iteration, which is the recursion’s disadvantage. Therefore, we need to choose recursion or iteration on a case-by-case basis. If running time is a major consideration, then iteration may be a better choice, but recursion may be more appropriate if code simplicity is a concern. After posting my assignments, I received some encouraging comments, which I appreciate. In addition, thanks to the professor’s question, I have deepened my understanding of recursion in the process of thinking about the problem.

Recursions in the RecursiveSyntax.java

After finishing the programming assignment, I furthered my understanding of Recursive Syntax. To be more specific, the prompts require students to write a program that generates random sentences based on seven syntax rules. Hence, I define a RecursiveSyntax class and 6 methods in the class: randomSentence(), randomSimpleSentence(), randomVerbPhrase(), randomItem(), and the main(). When I finish the codes, I summarize and find four recursion calls. First, the randomSentence() calls itself. Second, randomSimpleSentence() calls randomVerbPhrase(), and randomVerbPhrase() calls randomSimpleSentence() in return. Third, in randomSimpleSentence, randomNounPhrase is called; randomNounPhrase calls randomVerbPhrase, and randomVerbPhrase calls randomSimpleSentence. Therefore, this is also equivalent to randomSimpleSentence calling itself. Fourth, randomVerbPhrase() calls randomSimpleSentence(), and randomSimpleSentence() also calls randomSimpleSentence(), which is also equivalent to randomVerbPhrase() calling itself. As shown in the figure above, I visualize the recursive relationship, where different colored lines represent different recursive calls.

Codes:

public class Test {
    public static void main(String[] args) {
        xMethod(5);
    }

    public static void xMethod(int length) {
        while (length > 1) {
            System.out.print((length - 1) + " ");
            xMethod(length - 1);
        }
    }
}

Codes in Question 7 (UoPeople, 2022, para. 7)

To test and reinforce my knowledge this week, I took the self-quiz. There are two types of questions: The application of recursion and the definition of a linked list. After taking the test, I was impressed with two questions. First, there is a question about infinite recursion. The code given by the prompts is as above, and the tester is asked to choose the correct output. At first, I thought it was just a simple recursion, so I thought the answer was 4321. However, the correct answer is 4321111… Since recursion has many call stacks, it is not easy to analyze clearly. Therefore, I added breakpoints in the IDE to debug the program step by step, and finally, I understand why it keeps outputting 1. Second, there is another question about the definition of Fibonacci numbers. The three options in the answers are as follows: “(a) The Fibonacci series begins with 0 and 1, and each subsequent number is the sum of the preceding two numbers in the series; (b) the Fibonacci series begins with 1 and 1, and each subsequent number is the sum of the preceding two numbers in the series; (c) the Fibonacci series begins with 1 and 2, and each subsequent number is the sum of the preceding two numbers in the series” (UoPeople, 2022, para. 5). The given answer for the question is a. However, according to Wikipedia, “the Fibonacci sequence commonly starts from 0 and 1, although some authors omit the initial terms and start the sequence from 1 and 1 or from 1 and 2” (). So, to some extent, b and c are also correct because different authors may have different definitions. For instance, in this week’s exercise, the Fibonacci series defined in the prompt starts with 1 and 1.

Word count: 753

References

1.Eck, D. J. (2019). Introduction to Programming Using Java.
http://math.hws.edu/javanotes

2.University of the People. (2022). Self-Quiz Unit 2.
https://my.uopeople.edu/mod/quiz/review.php?attempt=6794824&cmid=279525

3.Wikipedia. (2022). Fibonacci number.
https://en.wikipedia.org/wiki/Fibonacci_number

​

---

This is the ending, thanks for reading.

---