Lab 09 - Recursion and Function Pointers (6 marks total)

This lab will focus on a new concept known as recursion. Recursion is simply when a function calls itself before terminating. Recursive functions are useful for developing many algorithms that require traversing through data structures. You have already seen some simple data structures this semester (arrays, linked list etc.). The reason recursion is frequently used because the actual code is typically simple and recursion often avoids nesting many loops/conditional statements.

A common bug with recursive algorithms is entering an infinite loop. A recursive infinite loop will normally cause a segmentation fault when the program runs out of memory, so be careful your segmentation fault is actually related to dynamic memory and not an infinite loop. Before entering new a block of code, the required memory for the variables is statically allocated. This static allocation uses "stack" memory where dynamic memory (malloc, realloc, etc.) is allocated from the "heap" memory. This means that each time a function is called, the required variables are allocated so the program will run out of "stack" memory. This is known as a stack overflow.

Pointers and recursion and generally accepted as the two difficult concepts in programming. If you can wrap your head both pointers and recursion early, you can become a better software developer.

There are two functions that you will need to write for this lab. The first function will swap the value of a string (char *) pointer. This swap function will accept two void pointers and swap the values. The Second, will be a recursive function that reverses the order of the strings in the list/array. When you find a solution, you will realize how simple the code in a recursive function can be. We will also use a function pointer for the swap function in the reverse function. This way the code will be more flexible making the program reusable reusable/dynamic.

Swap function accepting void pointers.

Recursive reverse list function.

In the lab09 directory include the following files,

recursiveReverse.c

Evaluation: (6 marks)

Swap function for swapping pointers (2 marks)

Recursive reverse list (4 marks)

You will receive a zero if recursion is not used

------------------------------------------------------------------------------------

%%file lab09/lab09.h

/* you are not submitting the lab09.h file, so do not change this file */

/***** * Standard Libraries *****/

#include #include #include

/***** * Function Prototypes for recursiveReverse.c *****/

/* Swap the value of two strings */ void swapString(void **a, void **b);

/* This is the recursiveReverse function that will reverse the order of a list */ void recursiveReverse(void **listPtr, int lowIndex, int highIndex, void (*swapFunction) (void **, void **));

----------------------------------------------------------------------------------------------

%%file lab09/recursiveReverse.c

#include "lab09.h"

----------------------------------------------------------------------------------------------

%%file lab09/main.c

#include "lab09.h"

int main(int argc, char *argv[]) { printf("Hello, World "); return 0; }