[gabehabe]

Recursion

First off, I'd like to say that I'm looking for more than just a tutorial on this one. I'd like to ask anyone who reads this to try to contribute with their own recursive methods, to use as an example, and also to discuss the benefits and disadvantages of recursion.

Recursion is a very interesting topic in programming. It takes a bit of practice to get used to it, so I'm going to include a few examples, written in C#, C++ and Java. Hopefully, they'll apply to you, but I'm adding pseudocode for those of you who specialise in other languages.


First, a little Q&A

WTF is recursion?
Recursion is a really neat way to write your functions. A simple definition of recursion would be this:
A recursive function is one which calls itself.

Basically, if you've ever written a function that called itself~ you were using recursion!

So, what are the benefits of using recursion?
Well, after you get a little used to using recursion, the key design benefits are:

• Code is clearer and easier to use
  
• The code can be much shorter, and easier to read

Along with these benefits, it forms a great hierarchical structure, performing the required task an unspecified number of times.

The greatest and most common example of where recursion really comes in handy is listing the contents of directories, sub directories, sub sub directories, etc. I'll be demonstrating how this can be done later, when we come to the examples.

Well, this recursion lark sounds pretty cool. What are the drawbacks?
As with anything in life, there are drawbacks, along with the benefits. These include:

• It can be hard to find bugs~ particularly when using global variables
  
• It takes quite a bit of practice to get used to
  
• Space~ not too big a problem in modern technology, but any local variables within the function have to be created over and over again
  
• Time~ the operations which affect the space often affect the time of the method

So, without further ado, let's get down to an example! This is a method to print a triangle in the console. Admittedly, it's not the most interesting method, but it's a simple demonstration of recursion. I'll write this in pseudocode, and follow it up with examples in C++ and Java.

void recursiveTriangle(int x) { // the function name, return type, and parameters. Nothing new here
	if (x == 0) return; // there's nothing left to print
	for (int i = 0; i < x; i++) // start a loop to print the stars for this row
	   print a star // print a star for this line
	print a new line character // end of the line, get ready for the next!
	recursiveTriangle(--x); // call the method again, with one less star to print on the row
}

So, for example, if we called this method like so: recursiveTriangle(4), the output would be:
****
***
**
*

So why is this? It's time to look at the structure, and see how this works:
First call, pass 4 (call #1)
...print 4 stars
...print a new line
...call self: recursiveTriangle(3) (call #2)
......print 3 stars
......print a new line
......call self: recursiveTriangle(2) (call #3)
.........print 2 stars
.........print a new line
.........call self: recursiveTriangle(1) (call #4)
............print 1 star
............print a new line
............call self: recursiveTriangle(0) (call #5)
...............Oh! it's 0!
............end call #5
.........end call #4
......end call #3
...end call #2
end call #1

Notice the hierarchical stucture, which I mentioned earlier? It's very systematic, isn't it?

As promised, here are the examples.

C++

void recursiveTriangle(int x) {
    if (x == 0) return; // do nothing else
    for (int i = 0; i < x; i++)
        cout << "*";
    cout << endl;
    recursiveTriangle(--x);
}

Java

public static void recursiveTriangle(int x) {
    if (x == 0) return; // do nothing else
    for (int i = 0; i < x; i++)
        System.out.print("*");
    System.out.print("\n");
    recursiveTriangle(--x);
}

Lastly, let's take a look at populating a TreeViews with the contents of directories, sub directories, files, etc.

Java
Note that I've also added a Boolean "recursive" so that the method can be used to scan either just one level, or all levels~

/*
 * @params: String directory ~ the directory to scan
 * @params: DefaultMutableTreeNode parent ~ the node to add any files as children
 * @params: Boolean recursive ~ determine whether to scan all subdirectories, or just the parent
 */
public static void listAllFiles(String directory, DefaultMutableTreeNode parent, Boolean recursive) {
	File [] children = new File(directory).listFiles(); // list all the files in the directory
	for (int i = 0; i < children.length; i++) { // loop through each
		DefaultMutableTreeNode node = new DefaultMutableTreeNode(children[i].getName());
		// only display the node if it isn't a folder, and if this is a recursive call
		if (children[i].isDirectory() && recursive) { 
			parent.add(node); // add as a child node
			listAllFiles(children[i].getPath(), node, recursive); // call again for the subdirectory
		} else if (!children[i].isDirectory()){ // otherwise, if it isn't a directory
			parent.add(node); // add it as a node and do nothing else
		}
	}
}

C#

/// <summary>
/// A method to populate a TreeView with directories, subdirectories, etc
/// </summary>
/// <param name="dir">The path of the directory</param>
/// <param name="node">The "master" node, to populate</param>
public void PopulateTree(string dir, TreeNode node) {
	// get the information of the directory
	DirectoryInfo directory = new DirectoryInfo(dir);
	// loop through each subdirectory
	foreach(DirectoryInfo d in directory.GetDirectories()) {
		// create a new node
		TreeNode t = new TreeNode(d.Name);
		// populate the new node recursively
		PopulateTree(d.FullName, t);
		node.Nodes.Add(t); // add the node to the "master" node
	} 
	// lastly, loop through each file in the directory, and add these as nodes
	foreach(FileInfo f in directory.GetFiles()) {
		// create a new node
		TreeNode t = new TreeNode(f.Name);
		// add it to the "master"
		node.Nodes.Add(t);
	}
}

I'm hoping to get a few more examples written, and hopefully others will contribute~ It might not be much, but any examples posted, I'll click that "This post was helpful" link to thank you.

[gabehabe]

Checking if a string is a palindrome
Using recursion: C/C++

Here's a ternary method, which is one line long. It's ugly, but it demonstrates recursion. It's written in C++

#include <string>
bool recursivePalindrome(std::string str, unsigned int index = 0) {
    return (str[index] == str[str.length()-index-1] ? recursivePalindrome(str, ++index) : index > (str.length()/2) ? true : false);
}

This is the same snippet, dulled down so that it's easier to read, still using recursion:

#include <string>
// by initialising index to 0 in our parameters, we give it a default value
// however, we can pass our own value later (which is what makes this recursive)
bool recursivePalindrome(std::string str, unsigned int index = 0) {
     // if we reached the half way point, we're good to go
    if (index > str.length()/2) return true;
    // if the character at [index] matches the character [length-index]
    // then we should continue
    else if (str[index] == str[str.length()-index-1])
        return recursivePalindrome(str, ++index);
    else return false; // otherwise, it's not a palindrome
}

And lastly, a C method written by baavgai:

int isPalindrome(char* str, int end) {
	if (end<1) { return 1; } // we've passed center, it's true
	if (str[0] != str[end]) { return 0; } // character doesn't match, it fails
	// note, we move the front one, the end one
	// then the end another one, to allow for the front movement
	return isPalindrome(str+1, end-2);
}

void checkPalindrome(char* str) {
	printf("'%s' is ", str);
	if(!isPalindrome(str, strlen(str)-1)) { printf("not "); }
	printf("a palindrome\n");
}

[westforduk]

Thanks for this! Really helpful!

[didgy58]

a very helpful tutorial indeed, its something ive been trying to get my head around the last few days, to try and streamline the code a little, thanks for this..

[absynthe]

Here's a neat little Java Example for ya GabeBabe!

import java.util.*;

public class RecursiveStars
{
	 static Scanner console = new Scanner(System.in);

	public static void main(String[] args)
	{
		int lines;

		System.out.print("Enter the number of lines in the grid: ");
		lines = console.nextInt();
		System.out.println();

		printStars(1, lines);

		System.out.println();
	}

	public static void printStars(int i, int lines)
	{

		int j;

		if(i <= lines)
		{
			for(j = 0; j < lines - i + 1; j++)
				System.out.print(" ");

			for(j = 1; j <= i; j++)
				System.out.print(" *");
			System.out.println();

			printStars(i+1, lines);

			if(i != lines)
			{
				for(j = 0; j < lines - i + 1; j++)
					System.out.print(" ");

				for(j = 1; j <= i; j++)
					System.out.print(" *");
				System.out.println();
			}
		}
	}

[gabehabe]

Harmonic Sum
Using recursion: C/C++

#include <iostream>

using namespace std;

float HarmonicSum (int n, float retval = 0.0f) {
    if (n > 0) {
        retval += (1.0f / n);
        return HarmonicSum(--n, retval);
    } else {
        return retval;
    }
}

int main() {
    cout << HarmonicSum(3);
    cin.get();
    return EXIT_SUCCESS;
}

[chili5]

That was really interesting and helpful. I keep getting problems in my contest prep like navigating mazes, and I don't have any idea to do it, since I don't know anything about recursive methods.

Very helpful

[RodgerB]

How are recursive methods any easier to read then iteration? Iteration has always been the most sensible readable option for me, but that may be because I program in .NET.

[gabehabe]

Maybe it's just personal opinion~ I personally think (once you've got the hang of recursion) that it's easier to read. It's just clearer.

Though I do have a strange way of looking at things. Maybe it's just me. If anyone else disagrees, let me know and I'll change it.

[gabehabe]

Recursively Remove a Folder and it's Contents
Written in C++

/*
 * A recursive function to remove a directory and it's contents
 * Author: Danny Battison
 * Contact: gabehabe@gmail.com
 */

#include <dirent.h>
#include <string>
using std::string;

bool IsDirectory(char path[]) {
    int i = strlen(path) - 1;
    if (path[strlen(path)] == '.') {return true;} // exception for directories
    // such as \. and \..
    for(i; i >= 0; i--) {
        if (path[i] == '.') return false; // if we first encounter a . then it's a file
        else if (path[i] == '\\' || path[i] == '/') return true; // if we first encounter a \ it's a dir
    }
}

bool RemoveDirectory(string path) {
    if (path[path.length()-1] != '\\') path += "\\";
    // first off, we need to create a pointer to a directory
    DIR *pdir = NULL; // remember, it's good practice to initialise a pointer to NULL!
    pdir = opendir (path.c_str());
    struct dirent *pent = NULL;
    if (pdir == NULL) { // if pdir wasn't initialised correctly
        return false; // return false to say "we couldn't do it"
    } // end if
    char file[256];

    int counter = 1; // use this to skip the first TWO which cause an infinite loop (and eventually, stack overflow)
    while (pent = readdir (pdir)) { // while there is still something in the directory to list
        if (counter > 2) {
            for (int i = 0; i < 256; i++) file[i] = '\0';
            strcat(file, path.c_str());
            if (pent == NULL) { // if pent has not been initialised correctly
                return false; // we couldn't do it
            } // otherwise, it was initialised correctly, so let's delete the file~
            strcat(file, pent->d_name); // concatenate the strings to get the complete path
            if (IsDirectory(file) == true) {
                RemoveDirectory(file);
            } else { // it's a file, we can use remove
                remove(file);
            }
        } counter++;
    }

    // finally, let's clean up
    closedir (pdir); // close the directory
    if (!rmdir(path.c_str())) return false; // delete the directory
    return true;
}

/** EXAMPLE USAGE **/
#include <iostream>
using std::cin;
using std::cout;
int main() {
    RemoveDirectory("C:\\New Folder");
    cin.get();
    return EXIT_SUCCESS;
}

[gabehabe]

Reversing a C-String (char array)
Language: C

Two ways, one is ternary. Just because I love it.

Full:

/*
 * Yet another method to reverse a string
 * Author: Danny Battison
 * Contact: gabehabe@gmail.com
 */

#include <stdio.h>
#include <string.h>

char* reverseCharArray(char str[], int pos) {
    int swap = (strlen(str)-1) - pos;

    if (swap < pos) {
        char temp = str[swap];
        str[swap] = str[pos];
        str[pos] = temp;
        return reverseCharArray(str, --pos);
    } else {
        return str;
    }
}

/** EXAMPLE USAGE **/
int main() {
    char str[] = "gabehabe is so freakin' awesome.";
    // remember, because an array is 0 based, we have to pass the length-1
    printf(reverseCharArray(str, strlen(str)-1));
    return 0;
}

Ternary:

/*
 * Yet another method to reverse a string
 * Author: Danny Battison
 * Contact: gabehabe@gmail.com
 */

#include <stdio.h>
#include <string.h>

char* reverseCharArray(char str[], int pos) {
    int swap = (strlen(str)-1) - pos;
    char temp = str[swap]; str[swap] = str[pos]; str[pos] = temp;
    return (swap < pos ? reverseCharArray(str, --pos) : str);
}

/** EXAMPLE USAGE **/
int main() {
    char str[] = "gabehabe is so freakin' awesome.";
    // remember, because an array is 0 based, we have to pass the length-1
    printf(reverseCharArray(str, strlen(str)-1));
    return 0;
}

[pc_w12ard]

very simple and elementary recursive calls, but very useful though.


add elements in a single array.

int sumArray( int [] x, int last)	 //last is length of array x-1
{
	 if(last<0)
		{ return 0;}
	 else{
		   return x[last] + sumArray(x, last-1);
		   }
}

Factorial of a number: n!= n*(n-1)!= n*(n-1)*. . .*2*1

int factorial(int n)
{
	 if(n<=0)
		 {return 1;}
	 else{
		 return n*fact(n-1);
			}
}

compute exponent: x^n

double exponent(int n, double x)	 //if n>=0
{
	if(n==0)
	   { return 1;}
	else{
		  return x* exponent(n-1, x);
		  }
}

multiply two integers by recursive addition

int multiply(int n, int m)
{
	 if(m==0)
		{return 0;}
	 else{
		  return n + multiply(n, m-1);
			}
}

[Jaakuuta]

First off, I wanted to add the factorial and a few more examples in a language that's well suited for recursion; LISP (well, Scheme, actually, but close enough)

; factorial example

(define fact
(lambda (x)
(if
(<= x 0)
1
(* x
(fact
(- x 1) ) )
)))

here's a method that applies the fact function just defined to a list of numbers

; factorial list example

(define factl
(lambda (x)
(if
(eq? x ())
x
(cons
(fact
(car x) )
(factl
(cdr x) ) )
)))

Here is that same function in Python

#factorial list example

def factl(x):
  if(x == []):
	return x
  else:
	return [fact(x[0]), factl(x[1:])]

here's a few recursive functions in Python that will
create a list of prime numbers and check to see if the number
you entered is a prime number

def checkPrime(y, z=[2]):
  if(z == []):
	return True
  elif((y % z[0]) == 0):
	return False
  else:
	return checkPrime(y, z[1:])

def primeList(x, y=2, z=[2]):
  if(x == y):
	if(checkPrime(y, z)):
	  z.append(y)
	return z
  else:
	if(checkPrime(y, z)):
	  z.append(y)
	y += 1
	return primeList(x, y, z)

These functions are neat because you don't have to rely on any internal variables. There are a few temporary default variables, but those are only there in case the user doesn't input those settings by default. Of course, they make it so that you can work with the functions either way and don't need any internal variables.