Writing Recursive Functions – Best Practices

algorithmsrecursion

I am having a lot of trouble writing recursive functions related to trees. I can't just use google for these functions as they are not general and I won't be able to use google in an exam setting!

Is there some 'trick' to successfully coming up with an algorithm/writing psuedocode for recursive functions? Is there a certain way I should think about/approach this?

Example: Write a recursive function that determines whether a given binary tree has a
structure consistent with a valid AVL tree.

Solution Expected: 

template <typename Type>
bool is_avl (const Binary_node<Type> * tree) {
    if (tree == NULL) {
        return true;
    }
    return is_bst (tree)
      && is_avl (tree->left())
      && is_avl (tree->right())
      && std::abs(height(tree->left()) - height(tree->right())) <= 1;
}

Best Answer

You're in luck! There (sort-of) is!

What you often want to do is identify the 2/3 cases:

  1. The base case
  2. The recursive case
  3. The exit case (sometimes optional)

That is:

  1. What you want to do
  2. Where you need to continue
  3. When you're done

Think of an example (DFS over a binary search tree):

bool DFS(Node currentNode, T searchValue)
{
    // base case
    if (currentNode.Value == searchValue) 
        return true;

    // recursive case and exit case
    if (curentNode.Left != null && DFS(currentNode.Left, searchValue)) 
        return true;

    // recursive case and exit case
    if (curentNode.Right != null && DFS(currentNode.Right, searchValue))
        return true;

    return false;
}

So here we have:

  1. Base case: whether we have found our value
  2. Recursive case(s): run DFS in the child nodes
  3. Exit case: return true if DFS on the child nodes found the value

So now think of in-order traversal of the same tree:

  1. Base case: print out the node
  2. Recursive case(s):
    • visit the left child
    • visit the right child
  3. Exit case(s): does the node exist?

In the case of in-oder traversal it looks like:

void InOrder (Node currentNode)
{
    // 3
    if (currentNode == null)
        return;

    // 2
    InOrder(currentNode.Left);
    // 1
    print(currentNode.Value);
    // 2
    InOrder(currentNode.Right);
}

Almost all recursive functions will have these elements. Identifying them and putting them in the right order is key.

Related Topic