Reverse a List

excerpt: This covers the basic idea of recursion, identifying the unit of work for each recursive call and doing the work after the recursive calls. tags: unit-of-work two-pointers reduce-input-by-one-unit

Write function that reverses a list in place.

Iterative Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def reverse(a)
  i = 0
  j = a.size - 1

  while i < j
    a[i], a[j] = a[j], a[i]
    i += 1
    j -= 1
  end
  
end

a = [10,4,3,5,2,9,14,3]

reverse(a)

p a

Recursive Implementation

Given the following input and output:

input {𝑎,𝑏,𝑐,𝑑,𝑒,𝑓,𝑔,h} 
output {h,𝑔,𝑓,𝑒,𝑑,𝑐,𝑏,𝑎}

How can we reverse the input to generate the given output?

Idea of Recursion

The first element must be processed by one of the recursive calls, the rest of the elements will be processed by other recursive calls.

𝑎 {𝑏,𝑐,𝑑,𝑒,𝑓,𝑔,h} 
{h,𝑔,𝑓,𝑒,𝑑,𝑐,𝑏} 𝑎

The unit of work in this case is processing one element in the input. The work is done after the recursive calls. It gets appended to the array during the return phase of the recursion. This is the key to understanding how the reverse method implements the recursive logic.

Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def reverse(a)
  if a.size == 1
    return
  end
  
  element = a.shift
  reverse(a)
  a << element
end

a = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

reverse(a)

p a

We can use the same concept to implement sorting. We can remove the minimum element from the list and insert it at the beginning.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def sort(a)
  if a.size == 1
    return
  end
  
  min = remove_min(a)
  # Reduce the input size by one unit
  sort(a)
  # Insert the minimum element at the beginning of the array
  a.unshift(min)
end

def remove_min(a)
  min = a.min
  a.delete(min)
end

a = [9, 3, 1, 8, 4, 0]

sort(a)

p a

The unit of work in this sorting method is processing one element. The unit of work is done after the recursive calls. The structure of this program is very similar to the reverse method implementation.

Building Blocks

• Two pointers
• Unit of Work
• Reduce Input by One Unit