beginner in recursion

[koopey]

Hi guys. I have this problem where I have to search for a value in the array and return the index of the array if the value is found. if value isn't found, it should return -1. all this to be done through recursive function.
here is my code.

#include <iostream>

int search(int array[],int i,int value_to_find)///i = index of array
{
    if(i<7&&array[i]==value_to_find)
    {
        return i;
    }
    else if(i<7&&array[i]!=value_to_find)
    {
        search(array,i++,value_to_find);
    }
    else
    {
    return -1;
    }
}


int main()
{
    int array[7];
    for(int i=0;i<7;i++)
    {
        array[i]=i+2;
    }
    std::cout<<search(array,0,25);
}

[keskiverto]

You forgot to formulate a question.

One thing that the compiler warns about:

 In function 'int search(int*, int, int)': 17:1: warning:
  control reaches end of non-void function [-Wreturn-type]

The thing is that
IF line 6 is true, then you do return i,
IF both lines 6 and 10 are false, then you return -1
but IF line 6 is false and line 10 is true, then you don't return anything


However, you do have an another issue too: the i++. There is also ++i. Do check how those two operators differ.

[koopey]

simply changing i++ to ++i made function work!
however,

but IF line 6 is false and line 10 is true, then you don't return anything

if so, i already called the search function(recursive) again. what else i do need to return?

[keskiverto]

Whatever the search returns.

On line 12 you do call a function (search) but you ignore its return value.
On line 28 you do call a function (search) but this time you do use the return value.
Does that look consistent?

[koopey]

The problem was:

Write a recursive function that takes a sorted array and a target element and finds that element
in the array (returning the index, or -1 if the element isn’t in the array)

so in this context, could you give an example, why and how can I use the return value?

[JLBorges]

> simply changing i++ to ++i made function work!

Favour pass by value using expressions without side effects; particularly in recursive code.
To pass (by value) an integer one greater that the current value of i, favour i+1 over either ++i or i++.

#include <iostream>

// return the index if the value is found; -1 if value isn't found
int find( const int array[], int array_size, int pos, int value_to_find ) // const
{
    // if we have reached the end of the array and not found the value
    if( pos >= array_size ) return -1 ;

    // if the value we are looking for is at index pos
    else if( array[pos] == value_to_find ) return pos ; 

    // recursively call find for positions on the right, starting at pos+1
    else return find( array, array_size, pos+1, value_to_find ) ; 
}

int main()
{
    const int N = 10 ;
    const int a[N] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    std::cout << find( a, N, 0, 0 ) << '\n' // 0
              << find( a, N, 0, 5 ) << '\n' // 5
              << find( a, N, 0, 9 ) << '\n' // 9
              << find( a, N, 0, 25 ) << '\n' ; // -1
}

http://coliru.stacked-crooked.com/a/e351ce7b9184f6cb

[koopey]

@JLBorges

else return find( array, array_size, pos+1, value_to_find ) ;

i now have a feeling of i am kind of getting it now. could you please help by clarifying why not:

else find( array, array_size, pos+1, value_to_find ) ;

where there is no "return" but the code would still work.

[JLBorges]

> where there is no "return" but the code would still work

Without the return, what you are seeing is 'undefined behaviour'

Undefined behaviour:

Anything at all can happen; the Standard imposes no requirements. The program may fail to compile, or it may execute incorrectly (either crashing or silently generating incorrect results), or it may fortuitously do exactly what the programmer intended. - C FAQ

[koopey]

Without the return, what you are seeing is 'undefined behaviour'

i didn't know that. but the scenario without "return" I was thinking/doubtful was:

i am calling recursive function with numerous stacks. the minute search function finds correct value, but say in 4th call. it returns index(pos) to the 3rd search function. then, without return, there would be no code to return correct value back to the first search function.

not sure if that is also true. is it?

[JLBorges]

> but say in 4th call. it returns index(pos) to the 3rd search function.
> then, without return, there would be no code to return correct value back to the first search function.
> not sure if that is also true. is it?

Yes.

This noisy version of the same program generates an annotated commentary of the return values.

#include <iostream>
#include <string>

static int depth = 0 ;

// return the index if the value is found; -1 if value isn't found
int find( const int array[], int array_size, int pos, int value_to_find ) // const
{
    if( pos == 0 ) depth = 0 ;
    else ++depth ;
    
    std::string tab( depth*2, ' ' ) ;
    tab += std::to_string(depth) + ". " ;

    std::cout << tab << "array_size: " << array_size << " pos: " << pos << " value_to_find: " << value_to_find << " => " ;
    // if we have reached the end of the array and not found the value
    if( pos >= array_size )
    {
        std::cout << value_to_find << " not found in positons 0 to " << array_size-1 << " - return -1\n" ;
        --depth ;
        return -1 ;
    }

    // if the value we are looking for is at index pos
    else if( array[pos] == value_to_find )
    {
        std::cout << value_to_find << " found at position " << pos << " - return " << pos << '\n' ;
        --depth ;
        return pos ;
    }

    // recursively call find for positions on the right, starting at pos+1
    else
    {
        std::cout << value_to_find << " not found at position " << pos << " - return find( ... " << pos+1 << " ... )\n" ;
        const int f = find( array, array_size, pos+1, value_to_find ) ;
        std::cout << tab << " find returned " << f << " - return " << f << '\n' ;
        --depth ;
        return f ;
    }
}

int main()
{
    const int N = 5 ;
    const int a[N] = { 0, 1, 2, 3, 4 };

    int f = find( a, N, 0, 0 ) ; std::cout << "\n *** result is " << f << " ***\n------------------\n" ; // 0
    f = find( a, N, 0, 2 ) ;  std::cout << "\n *** result is " << f << " ***\n------------------\n" ;// 2
    f = find( a, N, 0, 4 ) ; std::cout << "\n *** result is " << f << " ***\n------------------\n" ;// 4
    f = find( a, N, 0, 6 ) ; std::cout << "\n *** result is " << f << " ***\n------------------\n" ; // -1
}

> clang++ -std=c++14 -stdlib=libc++ -O3 -Wall -Wextra -pedantic-errors -pthread main.cpp && ./a.out

0. array_size: 5 pos: 0 value_to_find: 0 => 0 found at position 0 - return 0

 *** result is 0 ***
------------------
0. array_size: 5 pos: 0 value_to_find: 2 => 2 not found at position 0 - return find( ... 1 ... )
  1. array_size: 5 pos: 1 value_to_find: 2 => 2 not found at position 1 - return find( ... 2 ... )
    2. array_size: 5 pos: 2 value_to_find: 2 => 2 found at position 2 - return 2
  1.  find returned 2 - return 2
0.  find returned 2 - return 2

 *** result is 2 ***
------------------
0. array_size: 5 pos: 0 value_to_find: 4 => 4 not found at position 0 - return find( ... 1 ... )
  1. array_size: 5 pos: 1 value_to_find: 4 => 4 not found at position 1 - return find( ... 2 ... )
    2. array_size: 5 pos: 2 value_to_find: 4 => 4 not found at position 2 - return find( ... 3 ... )
      3. array_size: 5 pos: 3 value_to_find: 4 => 4 not found at position 3 - return find( ... 4 ... )
        4. array_size: 5 pos: 4 value_to_find: 4 => 4 found at position 4 - return 4
      3.  find returned 4 - return 4
    2.  find returned 4 - return 4
  1.  find returned 4 - return 4
0.  find returned 4 - return 4

 *** result is 4 ***
------------------
0. array_size: 5 pos: 0 value_to_find: 6 => 6 not found at position 0 - return find( ... 1 ... )
  1. array_size: 5 pos: 1 value_to_find: 6 => 6 not found at position 1 - return find( ... 2 ... )
    2. array_size: 5 pos: 2 value_to_find: 6 => 6 not found at position 2 - return find( ... 3 ... )
      3. array_size: 5 pos: 3 value_to_find: 6 => 6 not found at position 3 - return find( ... 4 ... )
        4. array_size: 5 pos: 4 value_to_find: 6 => 6 not found at position 4 - return find( ... 5 ... )
          5. array_size: 5 pos: 5 value_to_find: 6 => 6 not found in positons 0 to 4 - return -1
        4.  find returned -1 - return -1
      3.  find returned -1 - return -1
    2.  find returned -1 - return -1
  1.  find returned -1 - return -1
0.  find returned -1 - return -1

 *** result is -1 ***
------------------

http://coliru.stacked-crooked.com/a/8704d54b66e033fb

[koopey]

woooooohhh. that was highly explanatory. got it. thanks :D