Logo Questions Linux Laravel Mysql Ubuntu Git Menu

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

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

For example, consider the following string:


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


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)) {



            if (runLength>1){
        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)


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

like image 490
AChoi Avatar asked Mar 22 '23 12:03


1 Answers

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)) {

    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.

like image 179
lex82 Avatar answered Apr 26 '23 03:04