Recursion Question : Revision

Question

My slides say that:

• A recursive call should always be on a smaller data structure than the current one

• There must be a non recursive option if the data structure is too small

• You need a wrapper method to make the recursive method accessible

Just reading this from the slides makes no sense, especially seeing as it was a topic from before christmas!

Could anyone try and clear up what it means please?

Thank you

Answer 1

A recurssive call should always be on a smaller data structure than the current one

In general this isn't true but if you are talking about linked lists manipulation with recursion it is. What it is implying is that you need to always be working towards a solution and this usually is dealing with a smaller problem than you started with.

Take for example Quicksort. Each time the function is called it is working with a smaller set of data.

Taking another example of printing a linked list, the next time you call the recursive function the argument should be the tail of the linked list (This code has an error in it, but that leads us to our next point)

void printList(List l){
    print(l.head);
    printList(l.tail); 
}

There must be a non recurssive option if the data structure is too small

This means there should be a base case. The point where the function stops calling itself again.

int factorial(int n){
    if ( n == 1 ){ //the base case is when n = 1
        return 1;
    }
    return n*factorial(n-1);
}

Going back to the example of printing a linked list, there has to be a case where you only have an empty list left (in which case the function should do nothing). Going back to the code to print a linked list

void printList(List l){
    if ( l.empty == true ){ //the base case is when the list l is empty
        return;
    }

    print(l.head);
    printList(l.tail); 
}

You need a wrapper method to make the recurssive method accessible

I don't know Java, and it isn't really a language designed for recursion, however in many cases your recursive function will have more parameters than the person using the API should be able to see. You might for example want to have a counter in there.

You can have a wrapper function that simplifies the parameters to just what is needed. The wrapper function then calls the real worker function.

An example might be if we have a linked list class that has the recursive function to print the list. Its declaration would look something like this:

void printList(List l);

However as it is a class method, to someone using the API it doesn't make much sence to have to do this:

myList.printList(myList);

So a wrapper function could be created that doesn't have any paramters which then calls the code that does the work.

void printList(){
     doPrintList(this); //pass in the List object as the first argument
}

Then all the programmer using the API has to do is:

myList.printList();