Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I just had a doubt in my mind. The following subroutine(to search an element, in a list, for example) has a return statement at the end:

list *search_list(list *l, item_type x) {
  if (l == NULL) return(NULL);
  if (l->item == x)
    return(l);
  else
    return( search_list(l->next, x) );
}

I cannot get the significance of return statement at the end (i.e. return search_list(l->next, x) ). It would be really helpful if anyone could explain this concept, using stack model.

share|improve this question
    
If the first term of the list is not the result, search through the rest of the list. This is what the last return does. –  Giorgio Jun 17 '13 at 5:23
    
@Giorgio,Why wouldn't only a function call have sufficed,why a return is needed before that? –  user1369975 Jun 17 '13 at 5:29
7  
Because you need to return the value that is returned by the function –  Esailija Jun 17 '13 at 5:32
3  
Downvoters: please realize that, depending on the background of the OP, it's not at all obvious what return does. In fact, in functional languages (and some mixed ones, like Scala) return is not needed: the value of the recursive function is the value of its last expression. Simply writing search_list(l->next, x) without return would have worked in Scala! The meaning of the return statement is only obvious to programmers with an imperative background. –  Andres F. Jun 17 '13 at 13:29
    
OP: is your code snippet written in C? –  Andres F. Jun 17 '13 at 13:33
add comment

2 Answers

up vote 7 down vote accepted

A return statement passes a value back to the immediate caller of the current function's call-frame. In the case of recursion, this immediate caller can be another invocation of that same function.

In most languages, if you don't use the return value of a function you called (recursively or not), either that return value gets discarded or it is a diagnosable error. There are some languages where the return value of the last function call gets automatically re-used as the return value of the current function invocation, but they don't differentiate between normal and recursive function calls.

Assuming unused return values get silently discarded, if you had written the code like this:

list *search_list(list *l, item_type x) {
  if (l == NULL) return(NULL);
  if (l->item == x)
    return(l);
  else
    search_list(l->next, x); // no return!
}

then search_list would only return a defined value for an empty list (NULL) or if the first item matches the value you are searching for. As soon as the function goes into the recursive call, you don't know what the result will be, because the result of the recursive call gets discarded.

Additionally, you promise to return a value from your function, but you have a path (the recursive one) where you don't specify what value to return. Depending on the language you use, this usually results either in a mandatory diagnostic or in undefined behaviour (which is shorthand for: anything can happen and that can change at any time without notice. Don't hold anyone but yourself liable if it screws up your most important presentation). There are some situations where the missing return value might appear to work, but that might change the next time you run the program (with or without recompilation).

share|improve this answer
    
FWIW, Perl returns the result of the last expression automatically, which I think means it would reuse the return value. But I haven't touched it in years, so I'm not certain of that. –  Bobson Jun 17 '13 at 15:17
add comment

Two things; Returning the entire list in the case that you find the "x" you're looking for doesn't necessarily warrant using recursion, but that aside, consider the following:

Suppose you are seeking a value of X = "December", and your list is the numeric value of the months of the year, a pointer to the next month, and the l->items in the list are the spelled out names of the months. (January, February, ..., December). You need the three returns for the possible outcomes. The first, return(NULL) is needed if the list doesn't contain the X you're looking for. The second, (return(l)) returns the list, in this case, letting you know you found your "x". The last is where the stack model comes into play. Successive calls to the function would have updated local variables (specifically, l->item's) like this:

1: l->item = January
   returns search_list(l->next, x)
2: l->item = February
   returns search_list(l->next, x)
3-11: March, April, May, June, July, August, September, October, November
   all return search_list(l->next, x)
12: l->item = December
  This matches the second if() and returns your list, letting you know you found your search item.
share|improve this answer
    
,thanks for your illustration,but really don't get use of last return –  user1369975 Jun 17 '13 at 6:27
    
Without the last return, you never get past step 1. –  panhandel Jun 17 '13 at 6:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.