Return in Recursive Function

Returns in a recursive function

The recursive calls of the function do not influence on the returned value. Only the first return met in the first instance of your recursive function will return a value to the parent function. Any other return met will just stop the function's instance the program is currently in.

Thus as the function was called in main with the argument 0

int     i = 0;
i = recur(i);

The first return met is located inside of an if statement:

if (i < 3)
{
    recur(i + 1);
    return 10;
}

In this case, the recur function is called before returning a value to main. It will create another instance of recur which will do some stuff, but after this instance of recur has ended, the main instance of recur will continue and, in this case, will return 10 to the function main.

To know what your recursive function will return to the main function, you can simply comment all calls to a new instance of the function:

int     recur(int i)
{
    if (i < 3)
    {
        //recur(i + 1);
        return 10;
    }
    else if (i < 5)
    {
        //recur(i + 1);
    }
    return i;
}

In this case, this is what the program will read:

int     recur(int i)
{
    if (i < 3)
        return 10;
    return i;
}

Java return with recursion function

All recursive methods have three things:

1. An exit condition, to prevent an endless loop
2. A work item, and
3. A recursive call.

The exit condition in your recursive function is:

if (n == k)
   return;

The work item is:

n++;
System.out.println(n + " " + k);

Unless k is greater than n, in which case the work item is:

k--;
System.out.println(n + " " + k);

The recursive call is:

recTest (n,k);

Note that, since a return early-exits you out of the method, the else statement is not required.

To understand the behavior of a recursive method, you must first understand what a stack frame is, how the stack works, and how it serves to preserve state between method calls.

When Java prepares to call a method, it puts the calling methods' local variables including its parameters (collectively, the method's "state") and the return address of the calling method into a stack frame, and pushes that stack frame onto the stack. It then calls the new method.

When Java returns from a method, it pops the stack frame off the stack, restoring the calling method's original state.

A stack is like the stack of plates you see in the carousel at a 50's diner; the first plate off the stack is the last plate the dish washer put there. We call this a last-in, first-out (LIFO) queue.

With a little imagination, you can see how successive calls to a recursive method will keep a running history of any changes made to the state during each recursion. Since a copy of the state is saved during each recursion, you can walk back to a previous step in the state by returning from a method call.

Return function in recursion

There's nothing special to recursion - it's just plain functions calls and the fact that the function is calling itself is actually totally irrelevant -, and return works just the same as everywhere else.

Consider this:

def a(arg):
    return arg +1 

def b(arg):
    return a(arg * 2)

def main():
    result = b(42)
    print(result)

If you remove the return in b ie:

def b(arg):
    a(arg * 2)

then technically what you actually wrote is:

def b(arg):
    a(arg * 2)
    return None

since when they end up without an explicit return statement, Python functions implicitely return None. And as a result, in main(), result will be None instead of (arg * 2) + 1

It's the exact same thing happening in your code - if you don't explicitely return the result of the recursive call (=> once again, the fact it's a recursive call is technically totally irrelevant, it works exactly the same way), your function will return None, just has if you wrote:

    elif array[middle]>item:
        binary_search_recur(array,start,middle-1,item)
        return None
    else:
        binary_search_recur(array,middle+1,end,item)
        return None

Why does a recursive function call need to return a value to calling function?

The function definition says it will return an integer. If you do not put the last return the only the base case will return the value 0 and transfer the control to the previous (caller) function but no other return will be occur.

You probably do not need the return value in this case, and so you may use void as return in the function definition, and get rid of all the return altogether, however in many case you will need the return. One such simple example is to calculate the sum of 1...n integers as follows:

int sum(int n)
{
   if(n==0)
       return 0;
   return n + sum(n-1);
}

How to save the return value of a recursive function in a variable JavaScript

Your code: myFunction() will return void/undefined on first call, it is not a recursive approach.

Following example is a recursive approach. A recursive function usually receive an argument to be processed and return a final value that bubbles(returned) up to the first caller.

function myfunction(b){
  b--;
  if(b<3) return b;
  else return myFunction(b);
}

When you call a recursive function, you should prepare a test for an escape. Otherwise you might end up in an infinite loop.

Example of an infinite recursive

function badFunction(){
return badFunction();
}
// DON'T call badFunction()

Recursive Example

var b = 70;var safety = 1000;
function myfunction(local_b) {  if(safety<0) return;  safety--;
  // main task  local_b--;    if (local_b < 3) {    return local_b;  }
  return myfunction(local_b);
}var value = myfunction(b); // when b = 70, value = 2console.log(value);document.getElementById('value').innerHTML = value;

<span id="value">_</span>

---

Related Topics