Writing recursive functions

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

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.

• thanks, its good to have a method of coming up with the function as opposed to reaching out for some logic/algo in the dark! – rrazd Feb 22 '12 at 19:25

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.