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
– Aakash, Commented Sep 30, 2014 at 4:34
I suspect your first version relies on undefined behaviour to work. — Jonathan Potter
– Jonathan Potter, Commented Sep 30, 2014 at 4: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
– Code-Apprentice, Commented Sep 30, 2014 at 4:59

Code-Apprentice · Accepted Answer · 2014-09-30 04:34:39Z

1

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.

answered Sep 30, 2014 at 4:34

Code-Apprentice

84k26 gold badges163 silver badges290 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Jonathan Potter Over a year ago

This doesn't really answer the OP's question, which is why the return statements seemingly make no difference.

Community · Accepted Answer · 2017-05-23 11:57:42Z

0

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.

edited May 23, 2017 at 11:57

CommunityBot

11 silver badge

answered Sep 30, 2014 at 5:00

R Sahu

207k15 gold badges168 silver badges291 bronze badges

Collectives™ on Stack Overflow

return statement in Recursion: C++

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related