return statement in Recursion: C++

Question

I am trying to implement binary search tree and trying to implement searching the value from a node. The book implements it through recursion.

To understand the procedure better, I am trying to apply the logic on an array.

Consider below code:

#include <iostream>
#include "BST.h"


using namespace std;

char Array[]={'A','B','C','D','E','F','G','H','I','J'};

char fn(int i,int x)
{
 if( i == x)
 {
     cout << "Case : 1 " << endl;
     return Array[x];
 }

 else if( i > x)
 {
     cout << "Case : 2 " << endl;
    fn(--i,x);
 }
 else if(i < x)
 {
     cout << "Case : 3 " << endl;
     fn(++i,x);
 }

}


int main()
{

      cout << fn(2,7) << endl ;


    system("Pause");
return 0;
}

What I am trying to achieve is fn(int i,int x): from index i , search index x and return the value at index x.

The output is:
Case : 3
Case : 3
Case : 3
Case : 3
Case : 3
Case : 1
H
Press any key to continue . . .

The recursion logic works fine. But while compilation, it shows warning as main.cpp(28): warning C4715: 'fn' : not all control paths return a value

So if I modify my code as:

char fn(int i,int x)
    {
     if( i == x)
     {
         cout << "Case : 1 " << endl;
         return Array[x];
     }

     else if( i > x)
     {
         cout << "Case : 2 " << endl;
        return fn(--i,x);//added return here
     }
     else if(i < x)
     {
         cout << "Case : 3 " << endl;
         return fn(++i,x);//added return here
     }

    }

There is no compilation warning and output is exactly the same. My question is what purpose does return in each 'else if test condition' serve, I am returning from my base condition i.e. return Array[x]; and this is what I wanted my function to return. Why to put return in all the test conditions?

EDIT Just realized, second version of function still giving compilation warning main.cpp(30): warning C4715: 'fn' : not all control paths return a value What should be done? How to resolve?

After the control returns to your else if condition(back trace the recursion) it will have nothing to return. — Aakash, Sep 30 '14 at 04:34
I suspect your first version relies on undefined behaviour to work. — Jonathan Potter, Sep 30 '14 at 04:35
You could change your final `else if` to just `else`. I suspect that the compiler is not smart enough to see that your conditions cover all possibilities. — Code-Apprentice, Sep 30 '14 at 04:59

score 1 · Answer 1 · answered Sep 30 '14 at 04:34

My question is what purpose does return in each 'else if case' serve, I am returning from my base condition i.e. return Array[x]; and this is what I wanted my function to return. Why to put return in all the test conditions?

This returns the value from the base case ultimately to the top level of the recursive calls.

To understand this better, remember that return simply gives execution back to the function which called fn(). When fn() is called recursively, the caller and callee are both copies of the fn() function. You may call fn() recursively many times and each recursive call must return the result to its parent and ultimately back to the function which originally called fn().

I suggest you get a piece of paper and a pencil and work manually through an example input. Trace each recursive call of fn() and what happens when you return from each of these. After you do this by hand, use a debugger to step through your code to check that it works the way that you expect.

This doesn't really answer the OP's question, which is why the `return` statements seemingly make no difference. — Jonathan Potter, Sep 30 '14 at 04:54

score 0 · Answer 2 · edited May 23 '17 at 11:57

Without the return before fn(--i, x), and fn(++i, x), the function does not return from those statements. It tries to run any other statements that function might have. However, there aren't any. It reaches the end of the function without encountering a return statement.

A function whose return type is not void must have a valid return statement. Otherwise, the behavior of the code is undefined. You can read more about that at https://stackoverflow.com/a/1610454/434551.

The compiler is helping you avoid that problem by reporting warnings.

return statement in Recursion: C++

2 Answers2