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

• Bernard: Can you provide an example of a recursive function you are having trouble writing?
• Pubby: Can you give an example of the problem?
• James Snell: Possible duplicate of programmers.stackexchange.com/questions/136366/…

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.

• rrazd: 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!

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.