Midterm 2 Quiz

Midterm 2
What is recursion, and how does it differ from iteration?

• Recursion is a programming technique where a function calls itself repeatedly until a specific condition is met. Recursion can be thought of as a loop that repeats itself until a certain condition is met, but instead of using an explicit loop construct, it uses function calls.

• Recursion is a process where a function calls another function repeatedly, creating a chain of function calls that continues indefinitely, and it is similar to an infinite loop without the need for condition checking.

Midterm 2
What are the advantages and disadvantages of using recursion?

• Advantages
  1. Simplicity
  2. Flexibility
  3. Ease of Maintenance
  4. Conceptual Clarity
  
  Disadvantages
  1. Performance
  2. Debugging
  3. Complexity

• Advantages
  

  1. 1. Complexity

  2. 2. Rigidity

  3. 3. Difficulty of Maintenance

  4. 4. Conceptual Confusion
     

  1. 1. Disadvantages

  1. 2. Simplicity

  2. 3. Adaptability

  3. 4. Ease of Debugging

Midterm 2
Which two things you should always have in a recursive method?

• Base Case and Recursive call

• 1. Base Condition and Iterative Loop

• Recursive Statement and Break Statement

• 1. Starting Point and Looping Condition

Midterm 2
What is the base case in a recursive function, and why is it important?

• A base case is a condition that stops the recursion from continuing. It is the termination condition that is checked at the beginning of each recursive call. Without a base case, the recursive method would keep calling itself indefinitely, leading to an infinite loop.

• The base case is the condition that triggers the start of recursion, ensuring the function repeats until the base case is met.

• 1. The base case is an optional condition that is checked at the end of each recursive call, helping the recursion to continue.

Midterm 2
What is the recursive call in a recursive function, and how does it lead to the base case?

• The recursive case is the code that is executed when the base case is not met. It calls the same method again with a smaller or simpler version of the problem. This recursive call continues until the base case is reached.

• The recursive call is the code that is executed only when the base case is met. It calls the same method again with the same problem, ensuring that the base case is reached promptly.

Midterm 2
What are some examples of problems that can be solved using recursion?

• Calculating factorials: Computing the factorial of a number involves multiplying it by all the positive integers below it. This can be done using recursion by defining the base case as 0 or 1, and the recursive case as n * factorial(n-1).

• Solving linear equations: Recursive methods are commonly used to find solutions to linear equations by repeatedly applying mathematical transformations until the equation is balanced.

• Traversing a tree: Trees are a common data structure used to represent hierarchical relationships. Recursion can be used to traverse a tree by recursively visiting each node and its children.

• 1. Sorting arrays: Recursion is often employed to sort arrays by dividing them into smaller sub-arrays, sorting each sub-array, and then combining them.

Midterm 2
What is recursion, and how is it used in linked list algorithms?

• Recursion is commonly used in linked list algorithms because linked lists have a recursive structure, where each node contains a pointer to the next node in the list.
  
  In linked list algorithms, recursion is often used to traverse the list or perform operations on each node in the list. For example, to traverse a linked list recursively, you would define a function that takes a pointer to the current node as a parameter, and then calls itself with the next node in the list until the end of the list is reached.

• Recursion is an uncommon approach in linked list algorithms due to the non-recursive nature of linked lists. Linked lists are designed as linear structures with nodes containing pointers to the next node, making them better suited for iterative operations. In linked list algorithms, the conventional method involves utilizing iterative loops for traversing or manipulating nodes, providing a more efficient and straightforward solution compared to recursion, which tends to introduce unnecessary complexity.

Midterm 2
What is linear search, and how does it work?

• Simple search algorithm that checks every element in a list or array one by one until the target element is found, or the end of the list is reached. It works by checking each element in the list or array one by one, starting from the first element, until the target element is found, or the end of the list or array is reached.

• Linear search is a sophisticated algorithm that efficiently divides a list into segments, eliminating half of the elements at each step until the target element is located or the search space is reduced to a single element.

Midterm 2
What is binary search, and how does it work?

• Binary search is a searching algorithm that is used to find an element in a sorted list or array. It works by repeatedly dividing the search interval in half until the target element is found or the interval is empty.

• Binary search is a complex algorithm that involves random selection of elements from the list until the target element is located, providing a more intuitive search process.

• 1. Binary search is a linear search technique that checks each element in the sorted list one by one until the target element is found, similar to the linear search algorithm.

Midterm 2
How does the performance of linear search and binary search compare for large data sets?

• Binary search is faster than linear search for large data sets because it has a time complexity of O(log n), which grows slower than linear search's time complexity of O(n), binary search only works for sorted lists or arrays, while linear search works for any type of list or array.

• 1. Linear search outperforms binary search for large data sets since its time complexity of O(n) allows for quicker processing compared to the logarithmic growth in binary search.

  2. Binary search is slower than linear search for large data sets due to its intricate dividing approach, which introduces additional overhead in the search process.