Java Recursion – Can a Recursive Function Have Iterations?

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

Yes, some languages and complilers will convert recursive logic to non-recursive logic. This is known as tail call optimization - note that not all recursive calls are tail call optimizible. In this situation, the compiler recognizes a function of the form:

int foo(n) {
  ...
  return bar(n);
}

Here, the language is able to recognize that the result being returned is the result from another function and change a function call with a new stack frame into a jump.

Realize that the classic factorial method:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

is not tail call optimizatable because of the inspection necessary on the return.

To make this tail call optimizeable,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Compiling this code with gcc -O2 -S fact.c (the -O2 is necessary to enable the optimization in the compiler, but with more optimizations of -O3 it gets hard for a human to read...)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

One can see in segment .L4, the jne rather than a call (which does a subroutine call with a new stack frame).

Please note this was done with C. Tail call optimization in java is hard and depends on the JVM implementation -- tail-recursion + java and tail-recursion + optimization are good tag sets to browse. You may find other JVM languages are able to optimize tail recursion better (try clojure (which requires the recur to tail call optimize), or scala).