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( 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.

  • 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, 2013 at 5:23
  • @Giorgio,Why wouldn't only a function call have sufficed,why a return is needed before that? Jun 17, 2013 at 5:29
  • 9
    Because you need to return the value that is returned by the function
    – Esailija
    Jun 17, 2013 at 5:32
  • 10
    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, 2013 at 13:29
  • OP: is your code snippet written in C?
    – Andres F.
    Jun 17, 2013 at 13:33

2 Answers 2


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)
    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).

  • 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, 2013 at 15:17

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.
  • ,thanks for your illustration,but really don't get use of last return Jun 17, 2013 at 6:27
  • Without the last return, you never get past step 1.
    – panhandel
    Jun 17, 2013 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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