CODEWITHSUNDEEP
pythonrecursion
user1816377
user1816377

Reputation: 245

Find all indices with recursion

I have to write a program that finds all of the index values for specific element in list or a string. I have to use recursion, and my function can only take two arguments.

My problem is that my program finds only the first index and then stop. How can I change it to meet my requirements?

My code:

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

Input:

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

Desired output:

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

Upvotes: 1

Views: 4019

Answers (5)

user4343964
user4343964

Reputation: 

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; 
        } 
    }

Upvotes: 0

Robin
Robin

Reputation: 71

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] << " "; 
    } 
}

Upvotes: 0

Shaurya Khanna
Shaurya Khanna

Reputation: 1

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;
}

Upvotes: 0

Tyler Ferraro
Tyler Ferraro

Reputation: 3772

You can use Pythons ability to walk backwards through a list and grab the last element. Then put lists together with the + operator. By going through the list backwards you're able to find the indice when a value is found, rather than losing it when you move from the start of the list to the end.

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

Upvotes: 4

Vincent Savard
Vincent Savard

Reputation: 35927

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.

Upvotes: 1

Related Questions