Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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;
}
share|improve this question
    
Can you provide an example of a recursive function you are having trouble writing? –  Bernard Feb 22 '12 at 18:39
    
Can you give an example of the problem? –  Pubby Feb 22 '12 at 18:40

2 Answers 2

up vote 11 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.