java - Java递归；我怎样才能简化我所拥有的？

Question

我必须编写以下递归方法：

public static int countA(String s)

但是我发现如果不声明计数器和位置变量就不可能做到这一点。像这样：

public static int countA(String s, int position) {

        int count = 0;

        if( s.charAt(position) == 'A' )
            count++;

        if( position + 1 < s.length() ) {
            count += countA(s, position + 1);
        }

        return count;
    }

如何简化我的答案，以便我的方法与列出的方法相同？

编辑：是的，我想计算一个字符串中的所有 A。

Answer 1

尝试这个：

public static int countA(String s) {
    int count = 0;

    if (s == null)
        return 0;

    if (s.length() == 0)
        return 0;

    if (s.charAt(0) == 'A')
        count++;

    return count + countA(s.substring(1));
}

Answer 2

There are two forms of recursion,

• Tail Recursion : The return value is calculated as a combination of the value of current subroutine and the return value of the next call. Example,

  int factorial(int a) {
      if(a==0)
          return 1;
      else
          return a * factorial( a-1 );
  }
  

• Accumulator based recursion : You accumulate the results by adding an additional parameter and return the accumulated value.

  int factorial(int a, int fact) {
      if(a==0)
          return fact;
      else
          return factorial(a-1, a*fact);
  }
  

Obviously what you have here is accumulator based, while you can improve it to Tail recursion.

Tail recursion is considered more readable, while it can cause a StackOverflow! (no pun intended). This is because it has to push the current value to a stack, before calling subroutine again. And when you make a large number of such calls, this stack might go over its limit.

Some compilers optimize tail recursion to accumulator based in order to avoid this problem.

Answer 3

I think something like this should do the trick Here we are assuming that countA returns the number of As inside String s

public static int countA(String s)
{
    if(s.length()==0) return 0;  // return 0 if string is empty
    else
    {
        // if the first char is A add 1 to the answer, recurse
        if(s.toCharArray()[0])=='A') return 1+countA(s.subString(1,s.length()));

        // else add nothing to the answer, recurse
        else return countA(s.subString(1,s.length()));
    }
} 

Answer 4

You move the position variable out of the method and make it static(since your countA() is also static).

static int position = 0;
public static int countA(String s) {
    int count = 0;
    if( s.charAt(position) == 'A' )
        count++;
    if( position + 1 < s.length() ) {
        position++;
        count += countA(s);
    }
    return count;
}

Answer 5

关于什么：

public static int countA(String s) {
        if(s==null) return 0;
        if(s.length()==0) return 0;
        if( s.charAt(0) == 'A' )
        {
            return 1 + countA(s.substring(1));
        } else 
        {
            return countA(s.substring(1));
        }
    }

Answer 6

理想情况下，您首先具有终止条件，然后通常通过减少缩进/嵌套来简化代码，并对其执行“无操作”操作（通常需要比绝对需要多一次迭代）。

您也不需要局部变量！

public static int countA(String s, int position) {
    if (position == s.length())
        return 0;
    return (s.charAt(position) == 'A' ? 1 : 0) + countA(s, position + 1);
}