Recursion

Question 1

Unary v Binary v n-ary Recursion

Answer 1

Unary - single recursive call is used
Binary - two recursive calls are used (so maybe go left & right)
n-ary - n recursive calls

Question 2

Direct v Indirect recursion

Answer 2

Direct - recursive calls go to the same function
Indirect - recursion goes through two or more methods (p calls q, q calls p etc)

Question 3

Tail recursion

Answer 3

Where the result of the recursive call is the result of the function
(so nothing is done on the way back)

Question 4

Requirements for Recursion

Answer 4

1. base case/s
2. recursive call, where the result is combined
3. convergance to the base case (so it becomes more simple each time)

Question 5

Key Idea of Merge Sort

Answer 5

1. Split the array into two halves
2. Sort the smaller arrays
3. Merge two sorted halves into a single sorted array

Trival split, complex merge

Question 6

Merge Sort Psuedocode

Answer 6

Args: array, start, end, tmp array

if start != end:
- mid -> (start+end)//2
- recursive call (array, start, mid, tmp)
- recursive call (array, mid+1, end, tmp)
- call merge arrays (array, start, mid, end, tmp)

• copy array into temp from start to end - range(start, end+1)

Question 7

Merge Arrays (Merge Sort) Psudeocode

Answer 7

ia -> start index
ib -> mid index + 1

for i in range(start, end+1):
- if ia > mid: (meaning half1 is finished, use half2)
set tmp[k] to a[ib]
ib += 1
- elif ib > end: (meaning half 2 is finished, use half1)
set tmp[k] to a[ia]
ia += 1
- elif a[ia] <= a[ib]:
tmp[k] = a[ia]
ia += 1
- else
tmp[k] = a[ib]
ib += 1

Question 8

Quick Sort Psuedocode

Answer 8

Args: array, start, end

if start < end:
- boundary = partition(array, start, end)
- recursive_call(array, start, boundary-1)
- recursive_call(array, boundary+1, end)

complex split, no merge required

Question 9

Partition (quick sort) psuedocode

Answer 9

Args: array, start, end

mid -> (start+end)//2
pivot -> array[mid]
swap(array, start, mid)

boundary -> start

for k in range(start+1, end+1):
- if array[k] < pivot:
- boundary += 1
- swap(array, k, boundary)

swap(array, start, boundary)
return boundary

Question 10

Partition (quick sort) key idea

Answer 10

Pick a pivot (ideally the median)
move elements less than the pivot to the left, and greater than the pivot to the right

Question 11

Quick Sort complexity

Answer 11

Best Case: O(n log(n))Comp - when pivot is median
Worst Case: O(n^2)compeq - when pivot is max/min

Question 12

Merge Sort complexity

Answer 12

Best/Worst Case: O(n log(n))*Comp

Question 13

Merge Sort v Quick Sort v other sorts

Answer 13

Merge Sort:
- better complexity, lower number of comparisons
- however, requires a temp array, so way more space is needed

Quick Sort:
- worse complexity
- but no need to copy back, so a lower constant if the pivot is good

Other sorts:
- both of these require recursion, so overhead is higher, and may not be worth it for smaller arrays