How to Compress a String using Recursion? (RLE algorithm)

Question

I'm having slight trouble trying to compress a string using recursion.

For example, consider the following string:

qwwwwwwwwweeeeerrtyyyyyqqqqwEErTTT

After applying the RLE algorithm, this string is converted into:

q9w5e2rt5y4qw2Er3T

In the compressed string, "9w" represents a sequence of 9 consecutive lowercase "w" characters. "5e" represents 5 consecutive lowercase "e" characters, etc.

I already have a code for compressing it without recursion:

import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Compress {

    public static String input(String source) {
        StringBuffer coding = new StringBuffer();
        for (int i = 0; i < source.length(); i++) {
            int runLength = 1;
            while (i+1 < source.length() && source.charAt(i) == source.charAt(i+1)) {

                runLength++;   

                i++;

           }
            if (runLength>1){
            coding.append(runLength);
            }
            coding.append(source.charAt(i));
        }
        return coding.toString();
    }

    public static void main(String[] args) {

        IO.outputStringAnswer("Enter a string");
        String str = IO.readString();
        String result = ""; 
        result=input(str); //function(variable)


        IO.outputStringAnswer(result);
    }
}

But I am unsure if this is able to be turned into a recursion version of this.

You certainly can make a recursive version of it, but there's no clear benefit to doing so. — Jim Mischel
– Jim Mischel, Commented Nov 25, 2013 at 19:16
Oh, so I would have to rewrite the whole code? I'm still new to all this so I'm not very used to writing codes with recursion yet, sadly. — AChoi
– AChoi, Commented Nov 25, 2013 at 19:19
Why do you want to compress a string using recursion? I am having a hard time seeing a reason for doing so - at least in Java. — Vegard
– Vegard, Commented Nov 25, 2013 at 19:27
Oh it's part of an assignment I need to complete but I've never really used recursion in an assignment before until now. I've looked up some examples but I can't seem to figure out how to get recursion to be used for compression. — AChoi
– AChoi, Commented Nov 25, 2013 at 19:29
Does the assignment provide any guidance or justification for using recursion? This seems like a really bad use of recursion. — Jim Garrison
– Jim Garrison, Commented Nov 25, 2013 at 19:34

lex82 · Accepted Answer · 2013-11-25 21:09:57Z

5

This is most likely what you are looking for:

public static String compress(String source) {
    if (source.length() <= 1) return source;

    int runLength = 1;
    while (runLength < source.length() && source.charAt(0) == source.charAt(runLength)) {
        runLength++;
    }

    String lengthString = runLength > 1 ? String.valueOf(runLength) : "";
    return lengthString + source.substring(0,1) + compress(source.substring(runLength));
}

I assume your source String does not contain any digits. As you can see the function calls itself recursively in the last line with the remainder of the source string.

edited Nov 25, 2013 at 21:09

answered Nov 25, 2013 at 19:46

lex82

11.4k2 gold badges48 silver badges72 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Henry Florence · Accepted Answer · 2013-11-28 00:06:06Z

This is an interesting question. One solution that uses no iteration at all, only recursion would be:

public static String compressRecursion(String str, char curChar, int curCount) {
    // termination case - reached end of the source string
    if(str.length() == 0)
        return "" + (curCount == 1 ? "" : curCount) + curChar;

    // branch on change in next character
    String nextStr = str.substring(1,str.length());
    if(str.charAt(0) == curChar)
        return compressRecursion(nextStr,curChar,curCount + 1);
    else
        return "" + (curCount == 1 ? "" : curCount) + curChar
                + compressRecursion(nextStr,str.charAt(0),1);
}
public static String compress(String source) {
    return compressRecursion(source, source.charAt(0), 0);
}

This probably wouldn't be much use in production code, as a 'Stack Overflow' exception will occur with an input of any reasonable length, this is because a new stack frame will be created for every function call and thus character in the input. Java is not really designed to run code like this.

A synonymous compress function written in scheme (which has no iteration constructs):

(define (num2str num)
  (if (= 1 num) "" (number->string num)))

(define (first-char str)
  (substring str 0 1))

(define (next-string str)
  (substring str 1 (string-length str)))

(define (compress str char count)
  (cond [(= 0 (string-length str)) (string-append (num2str count) char)]
        [(string=? char (first-char str))
          (compress (next-string str) char (+ count 1))]
        [ else 
          (string-append (num2str count) char
            (compress (next-string str) (first-char str) 1))]))

(define (compressStart str)
  (compress str (first-char str) 0))

A functional language like scheme will use tail recursion optimisation to prevent stack overflow,and makes a function call a much more lightweight operation than in an imperative language like Java.

Collectives™ on Stack Overflow

How to Compress a String using Recursion? (RLE algorithm)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related