Writing recursive functions

Question

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;
}

Answer 1

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.

Answer 2

Is there some 'trick' to successfully coming up with an algorithm/writing psuedocode for recursive functions?

Absolutely! When you're writing a recursive function, you're explicitly describing the induction you're preforming on the given datastructure. Therefore, when you write your function, the 'trick' is twofold:

• Cover all the different forms your datastructure represents (IE, have cases for the leafs AND nodes of a tree, or the cells AND empty-lists in a linked list, or positive numbers AND zero if you're recurring on numbers.
• When you're dealing with the containing case (cell in a list, node in a tree), reduce the problem into subproblems and find a way to combine them if need be.

For example, here's a recursive function to count all the nodes in a tree:

def TreeCount(Tree):
    if Tree.isLeaf: # we can't go down any further
        return 1 
    else: # break the problem into sub-problems we can solve with this function
        return 1 + TreeCount(Tree.left) + TreeCount(Tree.right) 

As you can see, I split the function on the type of Tree we were looking at (Leaf vs Node) and in the case where I was dealing with a Node, I processed that in terms of recursions on it's subtrees.