Tag Archives: Recursion

Permutations in lexicographic order in C

This recursive algorithm produces the permutations in the most natural order, and is also the easiest to understand. It uses two buffers, one containing the permutation being built, and another for the remaining, unused letters.

The algorithm is:

if (there are no more characters to arrange) {
    print (the current permutation);
}
else {
    choose a remaining character;
    remove it from the remaining characters;
    add it to the permutation;
    use recursion to add the remaining characters to the permutation in the same way;
}

Here it is in C:

#include <stdlib.h>
#include <string.h>

typedef void(*permutationfn)(const char *);

static void permutations_recursive(char *perm, size_t used, char *remaining, size_t len,
        permutationfn fun)
{
    if (used == len) {
        perm[used] = '\0';
        fun(perm);
    } 
    else {
        const size_t unused = len - used;
        unsigned int i;
        for (i = 0; i < unused; i++) {
            /* Remove character at i from remaining */
            char c = remaining[i];
            memmove(remaining + i, remaining + i + 1, unused - i);
            /* Append it to perm */
            perm[used] = c;
            permutations_recursive(perm, used + 1, remaining, len, fun);
            /* Put character back */
            memmove(remaining + i + 1, remaining + i, unused - i);
            remaining[i] = c;
        }
    }
}

void permutations(const char *str, permutationfn fun)
{
    const size_t len = strlen(str);
    char *perm = malloc(len + 1);
    char *remaining = malloc(len + 1);
    if (perm && remaining) {
        strcpy(remaining, str);
        permutations_recursive(perm, 0, remaining, len, fun);
    }
    free(perm);
    free(remaining);

Example program:

#include <stdio.h>

int main(void)
{
    char str[] = "ABCD";
    permutations(str, (permutationfn)puts);
    return 0;
}

The output:

ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA

Reference: Exhaustive recursion and backtracking

Graph cycle detection in C

A cycle in a graph is simply a path whereby one can get from a vertex back to itself. For example, in the graph below there is a cycle (0, 1, 2, 3, 0).
Graph containing a cycle
A graph containing at least one cycle is called a cyclic graph, and a graph without cycles is called an acyclic graph.

Detecting whether a graph is cyclic or acyclic can be easily performed using a Depth First Search (DFS). We simply start at an arbitrary vertex, visit each of its neighbours, then each of the neighbour’s neighbours, and so on. If at any point we find a neighbour that we have visited already, and we haven’t just come from there, then we have detected a cycle.

Here is an implementation in C. Notice that, because it is a DFS, it is very similar to the connected components algorithm I described earlier, which also does a DFS.

#include <stdlib.h>

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

static unsigned int cyclic_recursive(const edge *edges, unsigned int n, unsigned int *visited,
        unsigned int order, unsigned int vertex, unsigned int predecessor)
{
    unsigned int i;
    unsigned int cycle_found = 0;
    visited[vertex] = 1;
    for (i = 0; i < n && !cycle_found; i++) {
        if (edges[i].first == vertex || edges[i].second == vertex) {
            /* Adjacent */
            const unsigned int neighbour = edges[i].first == vertex ?
                    edges[i].second : edges[i].first;
            if (visited[neighbour] == 0) {
                /* Not yet visited */
                cycle_found = cyclic_recursive(edges, n, visited, order, neighbour, vertex);
            }
            else if (neighbour != predecessor) {
                /* Found a cycle */
                cycle_found = 1;
            }
        }
    }
    return cycle_found;
}

unsigned int cyclic(const edge *edges, unsigned int n, unsigned int order)
{
    unsigned int *visited = calloc(order, sizeof(unsigned int));
    unsigned int cycle_found;
    if (visited == NULL) {
        return 0;
    }
    cycle_found  = cyclic_recursive(edges, n, visited, order, 0, 0);
    free(visited);
    return cycle_found;
}

An example program to find out if the graph shown at the top is cyclic or acyclic:

#include <stdio.h>

int main(void)
{
    const unsigned int order = 6; /* Vertices */
    const unsigned int n = 6; /* Edges */
    edge *edges;
    unsigned int c;
   
    edges = malloc(n * sizeof(edge));
    if (edges == NULL) {
        return 1;
    }

    edges[0].first = 0;
    edges[0].second = 1;
    edges[1].first = 1;
    edges[1].second = 2;
    edges[2].first = 2;
    edges[2].second = 3;
    edges[3].first = 3;
    edges[3].second = 0;
    edges[4].first = 3;
    edges[4].second = 4;
    edges[5].first = 3;
    edges[5].second = 5;

    c = cyclic(edges, n, order);
    printf("Graph is %s.\n", c ? "cyclic" : "acyclic");
    free(edges);

    return 0;
}

The output:

Graph is cyclic.

Connected components of a graph in C

A connected component of a graph is a maximal subgraph in which the vertices are all connected, and there are no connections between the subgraph and the rest of the graph. A connected graph has only one connected component, which is the graph itself, while unconnected graphs have more than one component. For example, the graph shown below has three components, (0, 1, 2, 3), (4, 5, 6), and (7, 8).
Graph with three connected components
The connected components of a graph can be found using a depth-first search (DFS). We start at an arbitrary vertex, and visit every vertex adjacent to it recursively, adding them to the first component. Once this search has finished, we have visited all of the vertices in the first connected component, so we choose another unvisited vertex (if any) and perform the same search starting from it, adding the vertices we find to the second component. This process continues until all vertices have been visited, at which point we know the number of connected components in the graph, and which vertices they contain.

This is an implementation of the connected components algorithm in C. An array is used to store the number of the connected component for each vertex, starting with component 0. The array elements are initialised to -1 so the array is also used to determine which vertices have not yet been visited, as their component number will still be -1.

#include <stdlib.h>

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

void connected_components_recursive(const edge *edges, unsigned int n, 
        int *components, unsigned int order, unsigned int vertex,
        unsigned int component)
{
    unsigned int i;
    /* Put this vertex in the current component */
    components[vertex] = component; 
    for (i = 0; i < n; i++) {
        if (edges[i].first == vertex || edges[i].second == vertex) {
            /* Adjacent */
            const unsigned int neighbour = edges[i].first == vertex ?
                    edges[i].second : edges[i].first;
            if (components[neighbour] == -1) {
                /* Not yet visited */
                connected_components_recursive(edges, n, components, order, neighbour, component);
            }
        }
    }
}

unsigned int connected_components(const edge *edges, unsigned int n, unsigned int order, 
        int **components)
{
    unsigned int i;
    unsigned int component = 0;
    *components = malloc(order * sizeof(int));
    if (components == NULL) {
        return 0;
    }
    for (i = 0; i < order; i++) {
        (*components)[i] = -1;
    }
    
    for (i = 0; i < order; i++) {
        if ((*components)[i] == -1) {
            connected_components_recursive(edges, n, *components, order, i, component);
            component++;
        }
    }
    return component;
}

Here is an example program that constructs the graph shown above and then finds its connected components:

#include <stdio.h>
#include <stdlib.h>

static void print_components(int *components, unsigned int order)
{
    unsigned int i;
    for (i = 0; i < order; i++) {
        printf("Vertex %u is in component %d\n", i, components[i]);
    }
}

int main(void)
{
    const unsigned int order = 9; /* Vertices */
    const unsigned int n = 8; /* Edges */
    edge *edges;
    int *components;
    unsigned int c;
   
    edges = malloc(n * sizeof(edge));
    if (edges == NULL) {
        return 1;
    }

    /* Square */
    edges[0].first = 0;
    edges[0].second = 1;
    edges[1].first = 1;
    edges[1].second = 2;
    edges[2].first = 2;
    edges[2].second = 3;
    edges[3].first = 3;
    edges[3].second = 0;

    /* Triangle */
    edges[4].first = 4;
    edges[4].second = 5;
    edges[5].first = 5;
    edges[5].second = 6;
    edges[6].first = 6;
    edges[6].second = 4;

    /* Line */
    edges[7].first = 7;
    edges[7].second = 8;

    c = connected_components(edges, n, order, &components);
    if (components == NULL) {
        free(edges);
        return 1;
    }
    printf("There are %u components:\n", c);
    print_components(components, order);
    free(edges);
    free(components);

    return 0;
}

The output:

There are 3 components:
Vertex 0 is in component 0
Vertex 1 is in component 0
Vertex 2 is in component 0
Vertex 3 is in component 0
Vertex 4 is in component 1
Vertex 5 is in component 1
Vertex 6 is in component 1
Vertex 7 is in component 2
Vertex 8 is in component 2

Recursive permutations in C

Recursion tree for a permutation algorithm

Another permutation algorithm in C, this time using recursion. I got this algorithm from Eitan Gurari’s CIS 680 lecture notes, which sadly are no longer online, although they are available on the Wayback Machine here: CIS 680: DATA STRUCTURES. I’ve stolen the image above, which shows a partial recursion tree, from him.

Here is the implementation:

#include <string.h>

typedef void (*permutationfn)(const char *);

static void swap(char *a, char *b)
{
    char temp = *a;
    *a = *b;
    *b = temp;
}

static void permutations_recursive(char *str, unsigned int left, unsigned int right,
        permutationfn fun)
{
    if (left == right) {
        fun(str);
    }
    else {
        unsigned int i;
        for (i = left; i <= right; i++) {
          swap(str + left, str + i);
          permutations_recursive(str, left + 1, right, fun);
          swap(str + left, str + i);
       }
   }
}

void permutations(char *str, permutationfn fun)
{
    permutations_recursive(str, 0, strlen(str) - 1, fun);
}

Example program:

#include <stdio.h>

int main(void)
{
    char str[] = "ABCD";
    permutations(str, (permutationfn)puts);
    return 0;
}

The output:

ABCD
ABDC
ACBD
ACDB
ADCB
ADBC
BACD
BADC
BCAD
BCDA
BDCA
BDAC
CBAD
CBDA
CABD
CADB
CDAB
CDBA
DBCA
DBAC
DCBA
DCAB
DACB
DABC

Finding out if a binary search tree is AVL recursively

A binary search tree with the AVL property has no node whose left and right heights differ by more than 1. AVL trees maintain this property by maintaining balance information in their nodes, and rebalancing themselves when they find the property has been violated.
It is possible, however, to determine whether a tree without any balance information has the AVL property by a depth-first search of the tree, checking the property at every node and propagating the result upwards.

typedef struct {
	unsigned int height;
	unsigned int avl;
} avl_info;

avl_info binarytree_avl_recursive(const btnode *node)
{
	avl_info info;
	info.height = 0;
	info.avl = 1;
	unsigned int leftheight = 0, rightheight = 0;
    if (node->left || node->right) {
        unsigned int leftavl = 1, rightavl = 1;
        avl_info child_info;
        if (node->left) {
            child_info = binarytree_avl_recursive(node->left);
            leftheight = child_info.height + 1;
            leftavl = child_info.avl;
        }
        if (node->right) {
            child_info = binarytree_avl_recursive(node->right);
            rightheight = child_info.height + 1;
            rightavl = child_info.avl;
        }
        if (leftheight > rightheight) {
            info.height = leftheight;
        } 
        else {
            info.height = rightheight;
        }
        info.avl = leftavl && rightavl && abs(leftheight - rightheight) <= 1;
    }
	return info;
}

unsigned int binarytree_avl(const binarytree *tree)
{
    unsigned int result = 1;
    if (tree->root != NULL) {
        result = binarytree_avl_recursive(tree->root).avl;
    }
    return result;
}

Counting internal nodes in a binary tree recursively

This is the counterpart of counting leaves in a binary tree recursively. If we are an internal node, we count 1 for ourselves, then recurse into the left and right subtrees and sum the count of internal nodes in them.

unsigned int binarytree_count_internal_nodes_recursive(const btnode *root)
{
    unsigned int count = 0;
    if (root->left != NULL || root->right != NULL) {
        count = 1;
        if (root->left != NULL) {
		    count += binarytree_count_internal_nodes_recursive(root->left);
	    }
        if (root->right != NULL) {
            count += binarytree_count_internal_nodes_recursive(root->right);
        }
    }
	return count;
}

unsigned int binarytree_count_internal_nodes(const binarytree *tree)
{
    unsigned int count = 0;
    if (tree->root != NULL) {
	    count = binarytree_count_internal_nodes_recursive(tree->root);
    }
    return count;
}

Counting leaves in a binary tree recursively

This is another recursive algorithm. If we are a leaf node, we return 1, and if not, we recurse into the left and right subtrees and return the sum of the leaves in them.

unsigned int binarytree_count_leaves_recursive(const btnode *root)
{
    unsigned int count = 0;
    if (root->left == NULL && root->right == NULL) {
        count = 1;
    }
    else {
        if (root->left != NULL) {
		    count += binarytree_count_leaves_recursive(root->left);
	    }
        if (root->right != NULL) {
            count += binarytree_count_leaves_recursive(root->right);
        }
    }
	return count;
}

unsigned int binarytree_count_leaves(const binarytree *tree)
{
    unsigned int count = 0;
    if (tree->root != NULL) {
	    count = binarytree_count_leaves_recursive(tree->root);
    }
    return count;
}

Finding out if a binary tree is a binary search tree recursively

A binary tree is a binary search tree (BST) if for every node, its left child’s value is less than its value, and its right child’s value is greater than its value.

This lends itself to a simple recursive algorithm for finding out if a binary tree is a BST.

unsigned int binarytree_is_bst_recursive(const btnode *node, int (*compare)(const void*, const void*))
{
    return 
        (node->left == NULL || 
        (compare(node->left->data, node->data) < 0 && binarytree_is_bst_recursive(node->left, compare)))
        &&
        (node->right == NULL ||
        (compare(node->right->data, node->data) > 0 && binarytree_is_bst_recursive(node->right, compare)));
}

unsigned int binarytree_is_bst(const binarytree *tree)
{
    unsigned int bst = 1;
    if (tree->root) {
        bst = binarytree_is_bst_recursive(tree->root, tree->compare);
    }
    return bst;
}

Boggle in Python

This is a solver for the game “Boggle”. The aim of the game is to find as many words as possible in a 4-by-4 grid randomly filled with letters. You are allowed to go up, down, left, right, or diagonally, but not use the same letter more than once.

First, here’s a prefix tree, which is the ideal structure for looking up words one letter at a time:

class PrefixTree(object):
    def __init__(self, letter=None):
        self.letter = letter
        self.children = {}
        self.stop = False

    def add(self, word):
        if len(word):
            letter = word[0]
            word = word[1:]
            if letter not in self.children:
                self.children[letter] = PrefixTree(letter);
            return self.children[letter].add(word)
        else:
            self.stop = True
            return self

    def find_letter(self, letter):
        if letter not in self.children:
            return None
        return self.children[letter]

    def __repr__(self):
        return "PrefixTree(letter={0}, stop={1})".format(self.letter, self.stop)

Here’s the code for the game solver itself. It simply searches recursively starting at each cell in the game, and looks up the sequences of letters it builds up in the prefix tree:

from random import choice
from prefixtree import PrefixTree

class Boggle(object):
    def __init__(self, board=None):
        self.size = 4
        if board is None:
            self.board = []
            for i in range(0, self.size):
                self.board.append([])
                for j in range(0, self.size):
                    self.board[i].append(Boggle.random_letter())
        else:
            self.board = board

    @staticmethod
    def random_letter():
        return chr(choice(range(65,91)))

    def play(self, tree, found):
        for r in range(0, self.size):
            for c in range(0, self.size):
                self.search_r(tree, found, r, c)

    def search_r(self, tree, found, row, col, path=None, node=None, word=None):
        letter = self.board[row][col]
        if node is None or path is None or word is None:
            node = tree.find_letter(letter)
            path = [(row, col)]
            word = letter
        else:
            node = node.find_letter(letter)
            path.append((row, col))
            word = word + letter
        if node is None:
            return
        elif node.stop:
            found.add(word)
        for r in range(row - 1, row + 2):
            for c in range(col - 1, col + 2):
                if (r >= 0 and r < self.size
                        and c >= 0 and c < self.size 
                        and not (r == row and c == col) 
                        and (r, c) not in path):
                    self.search_r(tree, found, r, c, path[:], node, word[:])

    def __repr__(self):
        return "Boggle(size={0}, board={1})".format(self.size, self.board)

I used this dictionary as a source of words. You may want to use a slightly smaller one.
Here is the main program:

def load_tree(tree):
    with open('dictionary.txt') as f:
        for line in f:
            word = line.rstrip().upper()
            tree.add(word)

def main():
    boggle = Boggle()
    tree = PrefixTree()
    load_tree(tree)
    found = set()
    boggle.play(tree, found)
    for word in sorted(found):
        print word
    print boggle

if __name__ == '__main__':
    main()

Finding the minimum depth of a binary tree recursively

This is the counterpart of finding the height of a binary tree recursively. We start with a depth of 0, and only if a node has 2 children, we add the minimum of their depths.

static int min(int a, int b)
{
    if (a <= b) {
        return a;
    }
    return b;
}

unsigned int binarytree_minimum_depth_recursive(const btnode *node)
{
    unsigned int depth = 0;
    if (node->left && node->right) {
        depth = min(binarytree_minimum_depth_recursive(node->left), 
                binarytree_minimum_depth_recursive(node->right)) + 1;
    }
    return depth;
}

unsigned int binarytree_minimum_depth(const binarytree *tree)
{
    unsigned int depth = 0;
    if (tree->root) {
        depth = binarytree_minimum_depth_recursive(tree->root);
    }
    return depth;
}