Recursion

Question 1

What use Recursion?

Answer 1

Allows solving complex problem with simple solution, reduces coding, and leads to efficient programs

Question 2

What is the recursive definition of factorial?

Answer 2

factorial(n) = n * factorial(n-1) with factorial(0) = 1

Question 3

what happens in the first call of factorial(4)?

Answer 3

Calls factorial(3)

Question 4

How does is factorial(4) broken down further?

Answer 4

4 * factorial(3)

Question 5

Expand factorial (4) to the next step

Answer 5

43(2* factorial(1))

Question 6

How does the recursion continue after 2 * factorial (1)?

Answer 6

2*(1 * Factorial(0))

Question 7

What is factorial (0)?

Answer 7

1.

Question 8

What does factorial(1) resolve to?

Answer 8

1 × 1 = 1.

Question 9

Simplify 4 × 3 × 2.

Answer 9

24

Question 10

Final result of factorial(4)?

Answer 10

24

Question 11

What is shown when tracing recursive factorial?

Answer 11

Each function call and its return path.

Question 12

What is the role of the stack in recursion?

Answer 12

It stores the state of each function call until it resolves.

Question 13

How does space usage grow during recursion?

Answer 13

Each recursive call adds a new frame to the stack.

Question 14

What is the recursive formula for sum(n)?

Answer 14

sum(n) = n + sum(n-1), with sum(0) = 0.

Question 15

How is sum implemented in Java?

Answer 15

Recursively adding n to sum(n-1) until n = 0.

Question 16

What is the recursive formula for Fibonacci numbers?

Answer 16

fib(n) = fib(n-1) + fib(n-2), with fib(0)=0, fib(1)=1.

Question 17

How does recursion flow for fib(4)?

Answer 17

Breaks into calls to fib(3) and fib(2) and so on.

Question 18

How is Fibonacci implemented in Java?

Answer 18

Recursively, with base cases for 0 and 1.

Question 19

What are two key features of a recursive method?

Answer 19

A base case and a reduction toward the base case.

Question 20

How can recursion be used to print a message n times?

Answer 20

Print once, then call recursively with (n-1) times.

Question 21

What is an example of solving a problem both iteratively and recursively?

Answer 21

Checking if a string is a palindrome.

Question 22

How does the non-recursive palindrome check work?

Answer 22

Using a while loop comparing characters from ends.

Question 23

What is a simple recursive palindrome check?

Answer 23

Compare first and last characters and recurse on substring.

Question 24

How can you improve the recursive palindrome check?

Answer 24

Use helper methods to avoid creating new substrings.

Question 25

What are examples of problems easier with recursion?

Answer 25

Binary search, selection sort, directory size, Tower of Hanoi.

Question 26

How does recursive binary search work?

Answer 26

Check middle, recurse on left or right half.

Question 27

What happens when recursive binary search fails to find a key?

Answer 27

Returns a negative insertion point.

Question 28

How does recursive selection sort work?

Answer 28

Find the smallest element, swap, then sort the rest recursively.

Question 29

What does the recursive selection sort code do after swapping?

Answer 29

Sorts the sublist from (low+1) to high.

Question 30

How is directory size computed recursively?

Answer 30

Sum sizes of files and recursively add sizes of subdirectories.

Question 31

In the getSize method, what is the base case?

Answer 31

When the file is not a directory.

Question 32

What is the Tower of Hanoi problem?

Answer 32

Move disks from one tower to another following rules.

Question 33

How is the Tower of Hanoi problem decomposed?

Answer 33

Move n-1 disks, move the largest disk, then move n-1 disks again.

Question 34

What is the recursive structure of moveDisks in Tower of Hanoi?

Answer 34

Move (n-1) disks, move disk n, move (n-1) disks again.

Question 35

What is a Sierpinski Triangle?

Answer 35

A fractal created by recursively subdividing triangles.

Question 36

How is a Sierpinski Triangle formed?

Answer 36

Connect midpoints and recurse on the three new triangles.

Question 37

Name 3 additional recursive problems discussed.

Answer 37

Sum of digits, reverse a string, compute GCD.

Question 38

What are the drawbacks of recursion?

Answer 38

High memory usage and extra time due to many stack frames.

Question 39

What is tail recursion?

Answer 39

A recursion where no pending operations remain after a recursive call.