algorithm - 查找字符出现的递归伪代码

Question

如果将字符串的字符放在数组中，如何使用递归找到特定字符的出现次数？我现在使用这个伪代码:

f(A[0;n-1],k)
if(n=0)then return;
c=0;
if(A[n-1]=k)then c++;`
return c+f(A[0;n-2],k)

Answer 1

让我们调用递归函数 f(S, c)，其中 S 是输入字符串。我们可以将 f(S, c) 表示为:

Base case: 
f(S, c) = 0, if length(S) == 0

General case:
f(S, c) = 1 + f(S[1:], c), if S[0] == c
        = f(S[1:], c), otherwise
where S[x:] denotes substring of S starting at xth index till the end.

换句话说，我们可以将其视为:假设我们知道较小子问题的答案，即从索引 1 开始到最后一个字符结束的子字符串。现在如果第 0 个字符匹配给定的字符串，我们的答案将简单地是 1 + 较小子问题的答案，否则我们的答案将是较小子问题的答案