python - 使用递归查找所有索引

Question

我必须编写一个程序来查找列表或字符串中特定元素的所有索引值。我必须使用递归，我的函数只能接受两个参数。

我的问题是我的程序只找到第一个索引然后停止。我怎样才能改变它以满足我的要求？

我的代码：

def find_all(L, v):
    return 0 if L[0] == v else 1 + find_all(L[1:], v)

输入：

1. find_all( [1,2,3,4,2,4,5,2,1], 2)
2. find_all("hello wonderful world", "w")

期望的输出：

1. [1,4,7]
2. [6,16]

Answer 1

您可以使用 Python 的能力在列表中倒退并抓取最后一个元素。然后将列表与 + 运算符放在一起。通过向后浏览列表，您可以在找到值时找到索引，而不是在从列表的开头移动到结尾时丢失它。

def find_all(L, v):
    if not L:
            return []

    result = []
    if L[-1] == v:
            result = [len(L)-1]

    return find_all(L[:-1], v) + result

Answer 2

You have to keep track of a counter somehow. The idea is to use find_all(L, v) as an interface to the "real" recursive function :

def find_all(L, v):
    return _find_all(L, v, 0)

def _find_all(L, v, position):
    # Your algorithm here

Considering this is homework, I will not do the work for you but you should be able to keep going from here.

Answer 3

Code in C++

 int allIndexes(int input[], int size, int x, int output[]){

 if(size==0)
      return 0;
    int ans=allIndexes(input, size-1, x , output );
    if(input[size-1]==x)
    {
        output[ans]=size-1;
       return ans+1; 
    }
    return ans;
}  

Answer 4

int AllIndexesRecursive(int input[], int size, 
                    int x, int output[]) 
{ 

    // If an empty array comes 
    // to the function, then 
    // return zero 
    if (size == 0) { 
        return 0; 
    } 

    // Getting the recursive answer 
    int smallAns = AllIndexesRecursive(input + 1, 
                                    size - 1, x, output); 

    // If the element at index 0 is equal 
    // to x then add 1 to the array values 
    // and shift them right by 1 step 
    if (input[0] == x) { 
        for (int i = smallAns - 1; i >= 0; i--) { 
            output[i + 1] = output[i] + 1; 
        } 

        // Put the start index in front 
        // of the array 
        output[0] = 0; 
        smallAns++; 
    } 
    else { 

        // If the element at index 0 is not equal 
        // to x then add 1 to the array values 
        for (int i = smallAns - 1; i >= 0; i--) { 
            output[i] = output[i] + 1; 
        } 
    } 
    return smallAns; 
} 

// Function to find all indices of a number 
void AllIndexes(int input[], int n, int x) 
{ 
    int output[n]; 
    int size = AllIndexesRecursive(input, n, 
                                x, output); 
    for (int i = 0; i < size; i++) { 
        cout << output[i] << " "; 
    } 
} 

Answer 5

Java code:
/ Java program to find all 
// indices of a number 
public class GFG { 
  
    public int[] AllIndexesRecursive(int input[], 
                                int x, int start) 
    { 
        // If the start index reaches the 
        // length of the array, then 
        // return empty array 
        if (start == input.length) { 
            int[] ans = new int[0]; // empty array 
            return ans; 
        } 
  
        // Getting the recursive answer in 
        // smallIndex array 
        int[] smallIndex = AllIndexesRecursive(input, x, 
                                              start + 1); 
  
        // If the element at start index is equal 
        // to x then 
        // (which is the answer of recursion) and then 
        // (which came through recursion) 
        if (input[start] == x) { 
            int[] myAns = new int[smallIndex.length + 1]; 
  
            // Put the start index in front 
            // of the array 
            myAns[0] = start; 
            for (int i = 0; i < smallIndex.length; i++) { 
                  
                // Shift the elements of the array 
                // one step to the right 
                // and putting them in 
                // myAns array 
                myAns[i + 1] = smallIndex[i]; 
            } 
            return myAns; 
        } 
        else { 
              
            // If the element at start index is not 
            // equal to x then just simply return the 
            // answer which came from recursion. 
            return smallIndex; 
        } 
    }