Week 3 - Recursive Thinking and Stacks Flashcards
What is an example of a problem and recursive solution?
Problem: search for a key in a box that contains many smaller boxes.
Recursive Solution:
Inspect a box
If another box is found, repeat step 1 (recursive call)
If the key is found, the search ends
What is Recursion?
Recursion is a process where a function calls itself to solve smaller instances of a problem. It continues until a base case is met, which stops the recursion. They always contain one base case and one recursive case.
What is a good rule of thumb for algorithms that can be implemented as a loop?
If an algorithm can be implemented as a loop, there is a way to implement it recursively.
What is a base case in a recursive function?
A base case is the condition in a recursive function that stops further recursive calls. It prevents infinite recursion by providing a direct solution for the simplest instance of the problem.
What is a recursive case in a recursive function?
A recursive case is the part of a recursive function that includes a call to the function itself to solve a smaller instance of the problem. It breaks down the problem until the base case is reached.
What is a Stack?
A stack is a basic data structure that follows the Last-In, First-Out (LIFO) principle, where the last item added is the first one removed. It can be implemented using either an array or a linked list.
What is the difference between the array and linked lists implementation of stacks?
Linked list implementation is easier than array, because they simply insert/remove the head of the list.
What is a Call Stack?
A call stack is a data structure that tracks active function calls, including each function’s local variables, parameters, and the location for resuming execution. It follows the LIFO principle, managing the execution flow and ensuring functions return to the correct place in the code.
What is the difference between “Push” and “Pop” in relation to call stacks?
“Push” refers to adding a function call to the top of the call stack when the function is invoked. “Pop” refers to removing the most recent function call from the stack when the function completes execution.
Why should you be careful when using call stacks?
Using the call stack simplifies managing recursion but consumes memory, as each function call requires its own allocation. To avoid memory issues from large call stacks, alternatives like loops or tail recursion can be used.
What is a parser?
A Parser is a program that takes text as input and evaluates the text based on a set of syntactic rules.
