Recursion

Any function that calls itself can be considered recursive. Recursion is a powerfully simple technique that is difficult to grasp at first. A recursive function is always composed of two cases; a base case and a recursive case.

The base case occurs when the recursive function reaches a fundamental unit of work that cannot be broken down any further.

The recursive case performs a small amount of work and passes on the rest through a recursive call to the same function but with different parameters. Omitting the base case will cause the function to recurse infinitely, or at least until the stack overflows.

The Fibonacci sequence is a commonly used example of a recursive algorithm. It looks like this: 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The next number is the sum of the previous two numbers. By definition, we'll say that the sequence begins with 1 and 1.

Practice Question: Write a recursive function that computes the nth value in the Fibonacci sequence; let the zeroth and first value be 1.

int fibonacci(int n) {
    if (n <= 1) // Check for the base case.
        return 1;
    else // Perform the recursive case.
        return fib(n - 2) + fib(n - 1);
}

Note that the running time of the solution above is very poor: O(2^n)!
Recursive algorithms are generally less efficient than iterative ones because of the overhead of the recursive calls on the stack.

A recursive algorithm can always be translated to use iteration. Even recursive algorithms with no obvious iterative solution can be implemented through the manual use of a stack. A good example is depth first search for trees.

Practice Question: Write the iterative equivalent of the Fibonacci function.

int fibonacci(int n) {
    int previous1 = 1;
    int previous2 = 1;
    int current = 0;
 
    for (int i = 0; i < n; i++) {
        current = previous1 + previous2;
	previous2 = previous1;
	previous1 = current;
    }
 
    return current;
}

Practice Question: Write a recursive binary search for integers.

public static int binarySearch(int[] search, int left, int right, int target) {
    int middle = (left + right) / 2;
 
    if (search[middle] != target) {
        if (left == middle || right == middle)
            return -1;
    }
    if (search[middle] < target) {
        return binarySearch(search, middle, right, target);
    }
    else if (search[middle] > target) {
        return binarySearch(search, left, middle, target);
    }
    else {
        return middle;
    }
}

Practice Question: Print all the possible permutations of a string; include repeats.

// with repeats
// Basically for a string of length n
// you swap each character into the leading string
// and then call permute_repeat on the remaining n-1
// characters. This way the case of permuting a string
// of length n is reduced to permuting a string of length
// n-1 and the base case is when length=1
void permute_repeat(string leading ,string str) {
    // base case where length is 1
    if (str.length() == 1) {
        cout << leading << str << endl;
        return;
    }
 
    // loop and swap each character to position 1 and permute
    for (int i = 0; i < str.length(); i++) {
        // swap spot i with 0
        char x = str[0];
        str[0] = str[i];
        str[i] = x;
        permute_repeat(leading+(str[0]), str.substr(1,str.length()-1));
    }
 
}
 
// this one avoids repeats
// for uniqueness just make sure that when you swap
// a character to position 1 that it is the earliest occurence
// of that charcter in the string
// This way uniqueness for strings of length n is reduced
// to uniqueness of strings of length n-1
void permute_unique(string leading, string str) {
    // base case where length is 1
    if (str.length() == 1) {
        cout << leading << str << endl;
        return;
    }
 
    // loop and swap each character to position 1
    for (int i = 0; i < str.length(); i++) {
        // check if str[i] is earliest occurence of the its character
        bool first_occurence = true;
        for (int k = 0; k < i; k++)
            if (str[k] == str[i])
                first_occurence = false;
        if (!first_occurence)
            continue;
 
        // swap spot i with 0
        char x = str[0];
        str[0] = str[i];
        str[i] = x;
 
        permute_unique((leading+str[0]), str.substr(1,str.length()));
    }
}

Webfaction is the ULTIMATE hosting platform for any serious developer.
SSH, WordPress, Rails, Django, cronjobs, compile and execute anything.
ProgrammingInterview.com is proudly powered by Webfaction.