HOW TO WRITE RECURSIVE FUNCTIONS ON YOUR OWN
In this tutorial, you’ll learn - well, you’ve already read the title - how to write recursive functions on yourown. If you’re the person to whom recursive functions are a mystery, then this tutorial is definitely for you.
Traditional books try to explain recursive functions with a well-known example – finding the factorial of anumber. And probably you’re desperately trying to find a book where different types of examples are
explained, because you’re asking yourself – “do we need to learn something so complex just for thisnonsense and of-no-use problem of finding factorials?” Grieve not. We’re here to the rescue! For the time
being, just forget what you already know about recursions. Let’s start with a real-life programming problem
and try to solve it with simple logics – without using recursion or such hard-to-understand concepts.
Our problem is very simple – we have to print the contents of a folder. However, the complex part of this is,there may be many children of that folder and each may contain again more children folders – we have toprint the names of all the folders in the hierarchy. To keep things simple, let’s assume there are no files
contained in any of the folders.
Now, how do we solve it? First, as depicted in figure 1, let’s assume there are only twochildren of the given folder. In this case, the given folder is the '/' (root) folder. Now, we caneasily write the following code (in Java) to print the names of the folders.
1 import java.io.File;2
3 public class FolderContentsPrint {4public static void main(String[] args) {5File root = new File("/");
6File[] folders = root.listFiles();
7for (File folder : folders) {8System.out.println(folder.getName());
9}
10}
11 }

Well, it was simple enough! Let’s try to think of a bit more complex situation – the folder acontains two children – c and d, but the folder b doesn’t contain anything (figure 2). Now,
we have to change the program to print the contents of the folder a along with the contentsof /. The added lines of code are highlighted with red text color.
1 import java.io.File;
23 public class FolderContentsPrint {4public static void main(String[] args) {5File root = new File("/");
6File[] folders = root.listFiles();
7for (File folder : folders) {8System.out.println(folder.getName());
9File[] subfolders = folder.listFiles();
10for (File subfolder : subfolders) {11System.out.println(subfolder.getName());
12}
13}
14}
15 }

So, that’s it. However, we can improve the readability of the program a bit. Consider the case of the folderb. It doesn’t contain any child. So, for that folder, the contents of the inner for loop (line 11) simply won’t
1execute as the subfolders array won’t contain any element. We can include a checking to see whether thesubfolders array contains any element, and if not, we won’t even consider touching the for loop. The
modified program might look as follows (the previously added lines are highlighted with green text color
and the newly added lines with red text color):
1 import java.io.File;2
3 public class FolderContentsPrint {4
public static void main(String[] args) {5File root = new File("/");
6File[] folders = root.listFiles();
7for (File folder : folders) {8System.out.println(folder.getName());
9File[] subfolders = folder.listFiles();
10if (subfolders.length > 0) {11for (File subfolder : subfolders) {12System.out.println(subfolder.getName());
13}
14}
15}
16}
17 }

Okay, let’s try to make it a bit more complex again. Now, we assume c contains twochildren named e and f (figure 3). So, we can edit the program again as follows:
1 import java.io.File;
23 public class FolderContentsPrint {4public static void main(String[] args) {5File root = new File("/");
6File[] folders = root.listFiles();
7for (File folder : folders) {8System.out.println(folder.getName());
9File[] subfolders = folder.listFiles();
10if (subfolders.length > 0) {11for (File subfolder : subfolders) {12System.out.println(subfolder.getName());
13File[] subSubfolders = subfolder.listFiles();
14if (subSubfolders.length > 0) {15for (File subSubfolder : subSubfolders) {16System.out.println(subSubfolder.getName());
17}
18}
19}
20}
21}
22}
23 }

Enough! Are we going to add lines of code for each folder level??? It’s totally absurd. We must find asimpler solution which would work for any level of folders. The question is – how?
Let’s take a closer look at the above program. Did you notice that lines 7-10 has been repeated in lines 11-14
with just a few changes in the names of variables used? If we were going to add more lines for the next levelof folders, we would repeat those same lines again. So, how can we get rid of this situation, i.e., eliminate
the repeating lines of code? There are two possible solutions – we can either execute a loop several times, orcall a procedure for some specific number of times. Let’s try to experiment with the second solution. We cancome back to the first one later.

2

So, we have to put the repeated lines of code into a function. Then let’s do it – just put those lines into afunction with a meaningful name – e.g. printFolders – and don’t bother with the function parameters andreturn types for now. The function should look like the following:
1 printFolders() {2for (File folder : folders) {3System.out.println(folder.getName());
4File[] subfolders = folder.listFiles();
5if (subfolders.length > 0) {
67}
8}
9 }

We have to fill up three gaps in the above function to make it a complete function – the parameters, return
type and the contents of the if statement (i.e., line 6). First, let’s try to find out the possible parameters ofthe function. To find them out, we have to dig into the code and try to detect any undeclared variables. Yep,you’ve got it – the variable folders is undefined. So, let’s define the folders variable as a parameter. Waita minute though – what about the type of this variable? If we look at the for loop, we can find that it is acollection – in this case, an array of File objects. Now, the return type. If we observe the code, we can cometo the conclusion that it doesn’t return anything. All that the function does is to print the names of thecontents of the folder. Therefore, the above function with return type and parameters should look like below:
1 void printFolders(File[] folders) {2for (File folder : folders) {3System.out.println(folder.getName());
4File[] subfolders = folder.listFiles();
5if (subfolders.length > 0) {
67}
8}
9 }

Now remains the final part – the contents of the if statement. As we’ve already learned, the lines 2-8 in theabove code will be repeated inside the if statement. But the printFolders() function contains all thenecessary repeating statements. Therefore, we can simply call the printFolders() function inside the ifstatement. However, this function needs an argument of type File[] to be passed when called. What should
it be in this case? The subfolders variable, of course. So, the complete function will look like thefollowing:
1 void printFolders(File[] folders) {2for (File folder : folders) {3System.out.println(folder.getName());
4File[] subfolders = folder.listFiles();
5if (subfolders.length > 0) {6
printFolders(subfolders);
7}
8}
9 }

To make the function a bit more readable, we can replace the parameter with just a File object. We can list
the contents of that File object inside the function:
123
456void printFolders(File root) {System.out.println(root.getName());
File[] folders = root.listFiles();if (folders.length > 0) {for (File folder : folders) {printFolders(folder);
3

789}
}
}

Our final program (which prints the contents of a given folder along with the name of that given folder)should look somewhat like below:
1 import java.io.File;2
3 public class FolderContentsPrint {45public static void main(String[] args) {6File root = new File("/");
7FolderContentsPrint obj = new FolderContentsPrint();
8obj.printFolders(root);
9}
10
11void printFolders(File root) {12System.out.println(root.getName());
13
File[] folders = root.listFiles();
14if (folders.length > 0) {15for (File folder : folders) {16printFolders(folder);
17}
18}
19}
2021 }

Done! You’ve written a recursive function! Now, before we formally state the steps for writing a recursivefunction, let’s try to grasp the process better.
At this point, we’ll examine the traditional factorial problem. The following program demonstrates how tofind the factorial of 5 using loop:
1 public class Factorial {2public static void main(String[] args) {3int number = 5, result = 1;
4for (int i = number; i > 0; i--) {5result = i * result;
6}
7System.out.println(result);
8}
9 }The above program can be re-written using a while loop instead of a for loop:
1 public class Factorial {2public static void main(String[] args) {3int number = 5, result = 1;
4while (number > 0) {5result = result * number;
6number--;
7}
8System.out.println(result);
9}
10 }There is no logical difference between these two versions of the program. Now, we’ll try to write theprogram using recursion. First, let’s focus on our target – obviously, it’s to find out the repeating lines ofcode. If we look at the while-loop version of the program, we can easily detect that lines 5 and 6 are thetargeted lines of code. (In case of the for-loop version of the program, however, it’s not obvious at first4

sight that i-- is also a part of the repeating statements; that’s why I also supplied the while-loop version.)
Therefore, according to our experience from the previous problem (printing the contents of a given folder),we have to put these two lines into a function – say, getFactorial(). We’ll be ignoring the return type andparameters for the time being.
1 getFactorial() {2
result = result * number;
3number--;
4 }Now, can’t we determine the parameters of this function? Of course! The variables result and number arenot defined. So, they must be the parameters. Okay, then what about the return type? It seems that thefunction returns nothing. So, the return type should be void. The function then becomes as follows:
1 void getFactorial(int result, int number) {2result = result * number;
3number--;
4 }So, where are we going to call the function recursively? It should be after the 3rd statement, something likebelow:
1 void getFactorial(int result, int number) {2result = result * number;
3number--;
4getFactorial(result, number);5 }Great! But hey, it’s going to recursively call the function infinite times! So, we must provide a condition onwhich the recursion will stop. What is it then? If we observe the while-loop version of the program, we canunderstand that the loop will continue while number > 0. So, our function should be calling itself as longas it finds that number > 0. The modified version of the function is as follows:
1 void getFactorial(int result, int number) {2result = result * number;
3number--;
4if (number > 0) {5getFactorial(result, number);6}
7 }Have we completed writing our recursive function for finding the factorial of a number? Sorry, the answer is‘no’. Why? Because, we need to get the value of result. As result is a local variable, when the function
will return, its value will be destroyed. However, among the different possible solutions, we’ll prefer one
solution (as it’s conceptually the easiest) – make the variable global. Our function might look like thefollowing then (the global variable isn’t shown here):
1 void getFactorial(int number) {2result = result * number;
3number--;
4if (number > 0) {5getFactorial(number);6}
7 }Our complete program should be somewhat similar to the following program:5

1 public class Factorial {2int result = 1; //the global variable [known as instance variable in java]
3
4
public static void main(String[] args) {5int number = 5;
6Factorial obj = new Factorial();7
obj.getFactorial(number);8
System.out.println(obj.result);
9}10
11void getFactorial(int number) {12result = result * number;
13number--;
14if (number > 0) {15getFactorial(number);
16}
17}
18 }

However, to make the program more efficient and professional, it can be thoroughly changed as follows:
1 public class Factorial {23public static void main(String[] args) {4int number = 5;5
Factorial obj = new Factorial();6
System.out.println(obj.getFactorial(number));
7}8
9
int getFactorial(int number) {10if (number > 0) {11return (number * getFactorial(number - 1));12} else {13return 1;
14}15}1617 }

Notice that the above program is conceptually advanced than our previous program. When you become
proficient in developing recursive functions, then you’ll be able to develop efficient recursive functions on
your own.
Our experiment with recursive functions is done. Now, finally, let’s take a look at the steps of writing arecursive function:
1.
2.
3.
4.

Determine the repeating statements in your program.
Just put those statements into a function with a suitable name.
Determine the parameters of the function by finding out all undeclared variables used inside it.
Determine the return type of the function by observing its behavior. In preliminary stages, you’lloften find that it is of type void. But when you become proficient, you’ll notice that by bringing
some changes into the body of the function, you can make the function return something and thus
make it more efficient and standard-looking.
5. Insert the recursive call to the function into an appropriate place within the function body.
6. Determine and add the necessary condition(s) to stop the function calling itself recursively infinite
times.
7. Make any necessary changes to the function to make it more efficient and professional.
Remember that you can convert loops into recursive functions and vice-versa.
6One final point before we conclude: Using recursive functions instead of loops doesn’t make your program
run more efficiently. Function calls are always expensive as various variables and register values arepushed-popped into and from the stack when a function is called or returned from. Then why on earth would
we use recursive functions at all?! The answer is simple – to make your program conceptually easier tounderstand.
So? What are you waiting for? Get your hands dirty by messing with recursive functions! NOW!!!

Sharafat Ibn Mollah Mosharraf
12th Batch (2005-2006),
Dept. of Computer Science & Engineering,
University of Dhaka.
E-mail: sharafat_8271@yahoo.co.uk
Home Page: www.sharafat.info
Blog: http://blog.sharafat.info

7