Recursion Flashcards

1
Q

What is a recursive subroutine?

A

A subroutine which is defined within itself, and calls itself.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What must all recursive subroutines have?

A

A base case (stopping condition), met at some point in the execution of the program.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What happens if a subroutine calls itself without a base case?

A

It will never terminate, infinitely looping which will lead to a stack overflow error due to more and more stack frames being pushed onto the call stack.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What other way can a problem often be solved if it can be solved recursively?

A

Through iteration.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the main difference between recursion and iterative solution?

A

Iterative solutions are often easier to program, whereas recursive ones are more compact in code.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What happens when you call a recursive subroutine?

A

The program counter and all local variables are pushed onto the stack.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What happens when you return a value from a recursive subroutine?

A

The stack is popped restoring the program counter and local variables.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a program counter?

A

A pointer storing the line number of the next instruction.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are some pros of using recursion?

A
  1. Simplified code
  2. Reduced code length
  3. Intuitive for Tree and Graph problems
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are some cons of using recursion?

A
  1. Higher memory usage
  2. Difficult to debug
  3. Limited by stack size
  4. Less control over execution
  5. Risk of infinite recursion
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is an alternative method of solution achieving the same functionality of recursion?

A

Iteration.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What are some uses of recursion?

A
  1. Traversing hierarchical structures
  2. Divide-and-conquer algorithms
  3. Backtracking problems
  4. Fractals and mathematical problems
How well did you know this?
1
Not at all
2
3
4
5
Perfectly