< Back

Lecture 19 - Recursion

---

As usual, create a directory to hold today's activities:

$ mkdir ~/cs170/labs/lab19 
$ cd ~/cs170/labs/lab19

---

Recursion

Similar to pointers, many people find the concept of recursion a little bit intimidating. However, recursion isn't really different from what we've seen so far in C++. It's just function calls. The difference, however, is that the function is going to call itself. We just need to make sure that the function knows when to stop.

---

Class Notes

recursion.cc

---

ANYTHING written using a loop, can be written using recursion! So today we will practice writing some of the loops we've seen before using recursion instead of using loops. One common loop we have seen (specifically in selection sort, for example) is a loop to find the smallest element in an array.

Details

In a file called recursion.cc, create a function called int findSmallest(int aList[], int length). This function should find and return the smallest element from the array. You should find the smallest element using recursion. You may need to define a helper function to help with this.

Make sure you test your function on several lists of various sizes, just to make sure that it works correctly.

Example

  int * my_list = new int[5];
  for(int i = 0; i < 5; i++) {
      my_list[i] = 5 - i;
  }
   
  cout << findSmallest(my_list, 5) << endl; //Prints 1

  delete[] my_sorted_list;

Hint

---

Bubble sort required 2 loops. One loop iterated through each index, comparing with neighbors and swapping until it reached the end of the array. The second loop made sure that the first loop executed N times. So, for bubble sort to be written recursively, you need two recursive functions.

Details

In your recursion.cc file, create a function called void bubble_sort(int * a_list, int size). This function takes an array of integers, and returns a sorted copy of a_list using the bubble sort algorithm. Instead of using loops this time, you should use recursion instead.

Example

  int * my_list = new int[5];
  for(int i = 0; i < 5; i++) {
      my_list[i] = 5 - i;
  }
  int * my_sorted_list = bubble_sort(my_list, 5);
  printList(my_list);         #Prints [5, 4, 3, 2, 1]
  printList(my_sorted_list);  #Prints [1, 2, 3, 4, 5]

  delete[] my_sorted_list;
  int my_list2[5] = {4, 2, 1, 3, 5};
  my_sorted_list = bubble_sort(my_list2, 5);
  printList(my_list2);         #Prints [4, 2, 1, 3, 5]
  printList(my_sorted_list);   #Prints [1, 2, 3, 4, 5]

Hint