What does this recursive function do?

Question

What does this function do? And how do you evaluate it?

How to trace it? How to understand recursive method?

I just can't understand the recursion, and the exam date is coming soon, and I know in order to understand recursion, I must first understand recursion.

But I just can't write a slightly complex recursive method, can anyone help me out using the simplest English words.

public class BalancedStrings {

    public static void printBalanced(String prefix, int a, int b) {
        if (a > 0)
            printBalanced(prefix + "a", a - 1, b);
        if (b > 0)
            printBalanced(prefix + "b", a, b - 1);
        if (a == 0 && b == 0)
            System.out.println(prefix);
    }

    public static void printBalanced(int n) {
        if (n % 2 == 0) {
            printBalanced("", n / 2, n / 2);
        }
    }

    public static void main(String[] args) {
        printBalanced(4);
    }
}

BTW I found some questions that deal with the same topic - http://stackoverflow.com/questions/3021/what-is-recursion-and-when-should-i-use-it, http://stackoverflow.com/questions/1011448/necessary-uses-of-recursion-in-imperative-languages. — verisimilitude, Jun 29 '12 at 15:23

Alex W · Accepted Answer · 2012-07-01T19:58:17.963

The calls to printBalanced() are the recursive calls. The way to recognize recursion is when a function is calling itself. Recursion is best understood when drawn using a tree:

enter image description here

The branches of the tree will continue to create more functions until an end condition is met, which in this case is a == 0 && b == 0. The function you provided looks like it is printing the string 'prefix' concatenated with a specified number of 'a' and 'b' characters, recursively. When the variables a and b reach 0, the recursion stops and the result is printed using System.out.println(prefix);

In the main function you are passing the integer 4 to printBalanced(int n) which the calls printBalanced(String prefix, int a, int b) with parameters like this: printBalanced("",2,2);

The overall result is prefix concatenated with a balanced number of a's and b's

score 0 · Answer 2 · answered Jun 29 '12 at 15:20

0

Your stopping condition is that

a == 0 & b == 0

Until this condition is met, you call the function recursively and lower a and b until they are both 0.

Try putting some breakpoints into printBalanced() so you can see how it works.

answered Jun 29 '12 at 15:20

Mark Nemec

119
1
2
12

score 0 · Answer 3 · answered Jun 29 '12 at 15:21

In the most basic computer science sense, recursion is a function that calls itself. Few practical usages of recursion.

Tree traversal
Graphs
Lexing/Parsing
Sorting

Basic idea of recursion is you take the original problem and divide it into smaller (more easily solved) instances of itself, solve those smaller instances (usually by using the same algorithm again) and then reassemble them into the final solution.

For example, consider the following C code of computing the factorial of a number

function factorial(int n)
{
  int fact = 1;
  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }
  return fact;
}

HeatfanJohn · Answer 4 · 2012-06-29T15:50:26.290

It may help you to see the recursion by placing print statements before each call to printBalanced and also a print statement as the first line of each printBalanced method definition. See below:

public class BalancedStrings {

    public static void printBalanced(String prefix, int a, int b) {
        System.out.println( "printBalanced called prefix = " + prefix + " a = " + a + " b = " + b );
        if (a > 0) {
            System.out.println( "printBalanced calling printBalanced with prefix = " + prefix + " a-1 = " + (a-1) + " b = " + b );
            printBalanced(prefix + "a", a - 1, b);
        }
        if (b > 0) {
            System.out.println( "printBalanced calling printBalanced with prefix = " + prefix + " a = " + a + " b-1 = " + (b-1) );
            printBalanced(prefix + "b", a, b - 1);
        }
        if (a == 0 && b == 0)
            System.out.println(prefix);
    }

    public static void printBalanced(int n) {
        System.out.println( "printBalanced called n = " + n );
        if (n % 2 == 0) {
            printBalanced("", n / 2, n / 2);
        }
    }

    public static void main(String[] args) {
        printBalanced(4);
    }
}

Also, printBalanced is also said to be an overloaded method because it has two "method signatures" which basically means that it is defined more than once and each method definition has a different set of variables that are passed to the method.

Basically, printBalanced will keep calling itself until variables a and b are decremented to zero. Then it will printout the resulting prefix that it keeps accumulating.

Also, all of this magic can happen because each method call will push the current state of prefix, a and b onto the call stack. The stack is then unwound when the method finally returns without making a recursive call.

I hope that this helps! Recursion can be difficult to understand. You can also trace the calls manually by playing computer yourself and tracing through the execution of the methods writing down on paper the values of prefix, a and b that will be pushed onto the call stack.

Here's the output of the program with the tracing prints included:

C:\Users\>java BalancedStrings
printBalanced called n = 4
printBalanced called prefix =  a = 2 b = 2
printBalanced calling printBalanced with prefix =  a-1 = 1 b = 2
printBalanced called prefix = a a = 1 b = 2
printBalanced calling printBalanced with prefix = a a-1 = 0 b = 2
printBalanced called prefix = aa a = 0 b = 2
printBalanced calling printBalanced with prefix = aa a = 0 b-1 = 1
printBalanced called prefix = aab a = 0 b = 1
printBalanced calling printBalanced with prefix = aab a = 0 b-1 = 0
printBalanced called prefix = aabb a = 0 b = 0
aabb
printBalanced calling printBalanced with prefix = a a = 1 b-1 = 1
printBalanced called prefix = ab a = 1 b = 1
printBalanced calling printBalanced with prefix = ab a-1 = 0 b = 1
printBalanced called prefix = aba a = 0 b = 1
printBalanced calling printBalanced with prefix = aba a = 0 b-1 = 0
printBalanced called prefix = abab a = 0 b = 0
abab
printBalanced calling printBalanced with prefix = ab a = 1 b-1 = 0
printBalanced called prefix = abb a = 1 b = 0
printBalanced calling printBalanced with prefix = abb a-1 = 0 b = 0
printBalanced called prefix = abba a = 0 b = 0
abba
printBalanced calling printBalanced with prefix =  a = 2 b-1 = 1
printBalanced called prefix = b a = 2 b = 1
printBalanced calling printBalanced with prefix = b a-1 = 1 b = 1
printBalanced called prefix = ba a = 1 b = 1
printBalanced calling printBalanced with prefix = ba a-1 = 0 b = 1
printBalanced called prefix = baa a = 0 b = 1
printBalanced calling printBalanced with prefix = baa a = 0 b-1 = 0
printBalanced called prefix = baab a = 0 b = 0
baab
printBalanced calling printBalanced with prefix = ba a = 1 b-1 = 0
printBalanced called prefix = bab a = 1 b = 0
printBalanced calling printBalanced with prefix = bab a-1 = 0 b = 0
printBalanced called prefix = baba a = 0 b = 0
baba
printBalanced calling printBalanced with prefix = b a = 2 b-1 = 0
printBalanced called prefix = bb a = 2 b = 0
printBalanced calling printBalanced with prefix = bb a-1 = 1 b = 0
printBalanced called prefix = bba a = 1 b = 0
printBalanced calling printBalanced with prefix = bba a-1 = 0 b = 0
printBalanced called prefix = bbaa a = 0 b = 0
bbaa

What does this recursive function do?

4 Answers4