Recursive List Operation in C++

Question

I was looking to create a function that takes in 2 arguments, an array and a key value, and recursively checks values of the array to see if they match the key.

To accomplish this, I need to check if the array is empty. I also need a way to call the array in my recursive function. I couldn't find anything on stack overflow to help, but I tried the method suggested in this Check if list is empty in C# post, and the code gave an error.

TLDR Need to figure out how to check if array is empty, and how to make recursive calls to a function that accepts an array as a parameter.

// recursive method: increment count for each recursive call; return the value of count when the key matches the value, then decrement count on
int Search::ReKeySearch( int arr[], int key){
//bool isEmpty = !list.Any();   tried to use this code, found on StackExchange, gave following error: "Cannot refer to class template 'list' without a template argument list"

if ( arr[count] == 0 ){ //if the key matches the list index's value
    store = count;  // so that I can reset count to zero, I use a storing variable
    count = 0;      // count should always be zero on exiting or entering a function
    return store;
}

else{
    count++;
    if ( /*need to check if list is empty*/ ){
        ReKeySearch(arr[1:], key);    //recursive call to function on list after zeroth member
                                      //returns error "expected ']'", pointing to the colon
        }// using pointer to attack problem of list index
    else
        ;
    count--;
}
if (count == 0)
    return -1;

}

You can write template function, and specialize case for 0, or, just use std::vector — Incomputable, Apr 28 '16 at 22:43
I meant to call the array from index 1 to the end of the array, but wasn't sure how to do that — cryptograthor, Apr 28 '16 at 22:43
Arrays in C++ are not objects like in other languages (ignoring the `std::array` class) and do not have any member functions to determine array length. Container objects in C++ do have this functionality and can be used to determine the number of items in the list. For example, `std::vector` has an `empty()` method as does `std::array`. The errors you are getting in your code are from using a type as a variable (`list.Any()` where `list` is a class template) and improper array access syntax (`arr[1:]` is a syntax error). — callyalater, Apr 28 '16 at 22:52
You are going to need to pass the capacity of the array because in C++ the capacity is not an attribute of the array and is lost when the array is passed. — Thomas Matthews, Apr 28 '16 at 22:53

score 0 · Answer 1 · answered Apr 28 '16 at 23:20

You can of course accomplish such a task with a simple loop, but, I am guessing that you want to do it recursively. I would do it as follows. Here is the link, if you want to experiment with it.

#include <iostream>
#include <vector>
using namespace std;

int searchHelper(const int arr[], int start, int stop, int key)
{
    if(start == stop)   return -1;
    if(arr[start] == key) return start;
    return searchHelper(arr, start + 1, stop, key);
}

int search(const int arr[], int size, int key)
{
    return searchHelper(arr, 0, size, key);
}

int search(vector<int> const& vec, int key)
{
    return searchHelper(vec.data(), 0, (int)vec.size(), key);
}

int main() {
    int arr[] = {3,10,2,5,6,1};

    cout << search(arr, 6, 10) << endl;
    cout << search(arr, 6, 20) << endl;

    return 0;
}

Note that I provided two approaches, one with arrays another using STL vectors. With vectors you don't have to keep the size of array separately. A similar approach can be used to do binary search if the array is sorted.

Recursive List Operation in C++

1 Answers1