java - 栈、堆和递归

Question

在可以使用递归(在堆栈中存储状态)和对象创建(在堆中创建新对象)的场景中。

问题

在对象创建和递归之间进行选择时应考虑哪些参数？

我的研究得出以下结论(需要验证这一点)

1. 当可用内存较少时:使用递归
2. 可读性:使用对象创建

范围:

• 我最关心的是内存和速度，速度优先。
• 如果可能的话，我关心的是可量化的事实和证据，而不是意见。

<小时/>

示例(在模式匹配算法中)

相关(代码审查SE):https://codereview.stackexchange.com/questions/59052/simple-wildcard-pattern-matcher-in-java-follow-up

使用递归和状态重置:

public class SimpleMatch {

    //state enums
    private static enum State {

        JUST_STARTED, NORMAL, EAGER, END
    }

    //constants
    private static final char MATCH_ALL = '*';
    private static final char MATCH_ONE = '?';

    private final int ptnOutBound; // pattern out bound
    private final int strOutBound; // string out bound
    private final String pattern; // pattern
    private final String matchString; // string to match

    private int ptnPosition; // position of pattern
    private int strPosition; // position of string
    private State state = State.JUST_STARTED; // state
    private boolean matchFound = false; // is match

    public SimpleMatch(String pattern, String matchStr) {

        if (pattern == null || matchStr == null) {
            throw new IllegalArgumentException(
                    "Pattern and String must not be null");
        }

        this.pattern = pattern;
        this.matchString = matchStr;
        int pl = pattern.length();
        int sl = matchStr.length();
        if (pl == 0 || sl == 0) {
            throw new IllegalArgumentException(
                    "Pattern and String must have at least one character");
        }
        ptnOutBound = pl - 1;
        strOutBound = sl - 1;
        ptnPosition = 0;
        strPosition = 0;

    }

    private void calcState() {
        //calculate state
        if (state == State.END) {
            return;
        }

        if (!patternCheckBound() || !matchStrCheckBound()) {
            state = State.END;
        } else if (patternChar() == MATCH_ALL) {
            if (!patternNextCheckBound()) {
                state = State.END;
                matchFound = true;
            } else {
                state = State.EAGER;
            }
        } else {
            state = State.NORMAL;
        }
    }

    private void eat() {
        //eat a character
        if (state == State.END) {
            return;
        }

        matchFound = false;

        if (state == State.EAGER) {

            int curStrPosition = strPosition;
            int curPtnPosition = ptnPosition;
            strPosition++;
            ptnPosition++;
            if (match()) {
                state = State.END;
                matchFound = true;
                return;
            } else {
                strPosition = curStrPosition;
                ptnPosition = curPtnPosition;
                state = State.EAGER;
            }
            strPosition++;
        } else if (state == State.NORMAL) {
            if (matchOne()) {
                strPosition++;
                ptnPosition++;
                matchFound = true;
            } else {
                state = State.END;
            }
        }
    }

    private boolean matchOne() {
        // match one
        char pc = patternChar();
        return (pc == MATCH_ONE || pc == matchStrChar());
    }

    private char patternChar() {
        // pattern current char
        return pattern.charAt(ptnPosition);
    }

    private char matchStrChar() {
        // str current char
        return matchString.charAt(strPosition);
    }

    private boolean patternCheckBound() {
        //pattern position bound check
        return ptnPosition <= ptnOutBound;
    }

    private boolean patternNextCheckBound() {
        //pattern next position bound check
        return (ptnPosition + 1) <= ptnOutBound;
    }

    private boolean matchStrCheckBound() {
        //string bound check
        return strPosition <= strOutBound;
    }

    /**
* Match and return result
*
* @return true if match
*/

    public boolean match() {
        if (ptnOutBound > strOutBound) {
            return false;
        }
        while (state != State.END) {
            calcState();
            eat();
        }
        return matchFound;
    }


}

使用新对象创建:

public class SimplePattern {

    //constants
    private static final char MATCH_ALL = '*';
    private static final char MATCH_ONE = '?';

    private final CharSequence pattern;
    private final int ptnPosition;

    public SimplePattern(CharSequence pattern) {
        this(pattern, 0);
    }

    private SimplePattern(CharSequence pattern, int ptnPosition) {
        if (pattern == null) {
            throw new IllegalArgumentException("Pattern must not be null");
        }

        this.pattern = pattern;
        this.ptnPosition = ptnPosition;
    }

    /**
     * Match and return result
     *
     * @return true if match
     */
    public boolean match(CharSequence string) {
        return this.match(string, 0);
    }

    public boolean match(CharSequence string, int startPosition) {
        if (ptnPosition == this.pattern.length()) {
            return startPosition == string.length();
        }
        if (startPosition >= string.length()) {
            return false;
        }
        SimplePattern nextPattern = new SimplePattern(pattern, ptnPosition + 1);
        char patternChar = this.pattern.charAt(this.ptnPosition);
        switch (patternChar) {
          case MATCH_ONE:
            return nextPattern.match(string, startPosition + 1);
          case MATCH_ALL:
            for (int i = startPosition + 1; i <= string.length(); i++) {
                if (nextPattern.match(string, i)) {
                    return true;
                }
            }
            return false;
          default:
            return string.charAt(startPosition) == patternChar &&
                   nextPattern.match(string, startPosition + 1);
        }
    }

}

Answer 1

我不认为对象创建与递归有任何关系。如果你的意思是循环，那么我的看法是:

When readability matters and time is scarce to implement: Recursion

When performance matters and iterations are many (especially in language like Java where there is no tail recursion): Loop