tags:

views:

352

answers:

5

Hey I'm working on a problem where you would print a string vertically using recursion. I know how to do this if i were to use a for loop:

for (int i = 0; i < str.length(); i++) {

   System.out.println(str.charAt(i));

but i'm not entirely sure how to do it using recursion. I took care of the base case but i'm not sure how to continue:

if (str == null || str.equals("")) {

    return str;

Any help will be greatly appreciated. Thanks!!!

A: 

Why would you want to do something like this? This is clearly a case where an iterative process would be clearer and easier to implement than a recursive implementation.

There are a few ways to handle this recursively. Since you are working with Java, I would recommend that you look at the String.substring method in the java core library.

bogertron
A: 

When in doubt, you can always translate iteration directly into recursion:

for (int i = 0; i < str.length(); i++)
    System.out.println(str.charAt(i));

...becomes:

public void printVertical(String str, int i) {
    if (i < str.length()) {
        System.out.println(str.charAt(i));
        printVertical(str, i + 1);
    }
}

String inputStr = ...
printVertical(inputStr, 0);

Note that there are many ways of doing this that are more elegant. This feels like a homework assignment to me. I would suggest you find one of the subjectively better approaches rather than using my "blind translation" of your loop.

Daniel Spiewak
better than using substring
Murali VP
I disagree. The better solution is to use `substring` as it is employing more of a "divide and conquer" approach. My "solution" is merely a loop in disguise.
Daniel Spiewak
A: 

This should do the trick:

void foo (final String str) {
    if (null != str && str.length > 0) {
        System.out.println(str.charAt(0))
        foo(str.substring(1))
    }
}

The point of recursion is that you have a function that calls itself.

AWhitford
A: 

The key to understanding recursion is understanding recursion. (bah dum bum)

But seriously, you should think about this in terms of making a smaller problem from the problem that you already have. In this example, you have a string of some length; how could you print part of that string and then have a smaller string with which to repeat the process? That's the essential idea of recursion.

Your base case is correct, so one way you could go about it using the Java libraries and your code above:

public String printVertical(String str)
{
    if (str == null || str.equals(""))
    {
        return str;
    }
    else
    {
        System.out.println(str.charAt(0));
        return printVertical(str.substring(1, str.length);
    }
}
Feanor
why are you returning str? Btw you method prototype is void
Murali VP
You're absolutely right, I am busy thinking about trees for an assignment of my own and am apparently a bit fuzzy. Corrected!
Feanor
+1  A: 
public void printVertString(String str) {
    if (str != null && str.length > 0) //1 base condition
    {
        System.out.println(str.charAt(0)) //2 print first char
        printVertString(str.substring(1)) //3 recursive call, but first char is omitted
    }
}

What this does:

  1. Check that the string is not empty (the base case). If it is, then there shouldn't be any more recursion and the method just returns without doing anything
  2. Print the first character of the string
  3. Calls itself, but only with the second character onwards

So if you send it a str = "CAT", the following is what happens (indents differentiate the different calls of the same function)

1 str is "CAT" --> not empty
2 print "C"
3 call printVertString "AT"
    1 str is "AT" --> not empty
    2 print "A"
    3 call printVertString "T"
        1 str is "T" --> not empty
        2 print "T"
        3 call printVertString ""
            1 str is "" --> EMPTY
            return
bguiz