1

I would like to know about the possible benefits of using or creating recursive functions in java applications.So, please enlighten me on where it is useful and we can get benefits of recursive calls.But I think, it takes more processing time than normal function.So, Why we use recursive calls in JAVA application?

Saravanan
  • 11,372
  • 43
  • 143
  • 213
  • possible duplicate of [What are the advantages and dis-advantaged of recursion?](http://stackoverflow.com/questions/5250733/what-are-the-advantages-and-dis-advantaged-of-recursion) – COD3BOY Dec 20 '11 at 09:29

8 Answers8

6

Sometimes recursion helps you to design simpler and more readable code. It is especially relevant for recursive data structures (like trees) or recursive algorithms.

The advantage is that you do not have to preserve state on each iteration. The JVM does it for you in form of call stack.

The disadvantage of recursive is that it requires more resources and its depth is limited by JVM.

AlexR
  • 114,158
  • 16
  • 130
  • 208
5

Recursive functions are used simply because for many algorithms they are a natural way to implement them.

A good example is the factorial() function:

function factorial(n) {
    if (n <= 1) {
         return 1;   // terminates the recursion
    } else {
         return n * factorial(n - 1);
    }
}

In many cases if the recursive call is the last action taken by the function ("tail recursion") then an iterative function may be used just as easily. The factorial() function above can be written like this:

function factorial(n) {
    var f = 1;
    for (var i = 2; i < n; ++i) {
        f *= i;
    }
    return f;
}

The performance of a recursive function is generally no worse than an iterative function, unless the recursive call tree grows non-linearly.

An example of that is the Fibonacci Sequence - f(n) = f(n - 1) + f(n - 2).

function fib(n) {
    if (n <= 2) {
        return 1;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

Since it recurses twice each time the function is called it is not as efficient as simply iterating from 1 to n - the recursive version has complexity at least O(2^n) whereas the iterative version is O(n).

Alnitak
  • 334,560
  • 70
  • 407
  • 495
2

Popular examples are binary search and quicksort. Both are divide and conquer algorithms.

If you wouldn't use recursion you would have to do the bookkeeping your self on external datastructures (stack). In the mentioned cases the status information is keept on the call stack and you don't need additional administration. So in some cases they lead to elegant and performant implementations.

stacker
  • 68,052
  • 28
  • 140
  • 210
1

Usually there is algorithms that look more clear, when implemented with recursion (For example Fibonacci sequence).

Recursion is very dangerous and should be well tested. In normal application there is no reason to use recursion since it can lead to problems.

Valchev
  • 1,490
  • 14
  • 17
1

yes, it takes more processing time and more memory.But there can be cases, when recursion is the best way.
For example if you need to get full tree of a directory and store it somewhere.You can write loops but it will be very complicated.And it will be very simple if you use recursion.You'll only get files of root directory, store them and call the same function for each of subdirectories in root.

shift66
  • 11,760
  • 13
  • 50
  • 83
  • just wonder - why would you say that? where is the overhead of the recursive functions? after all they are just normal functions, aren't they? – Deian Dec 20 '11 at 09:29
  • yes, they are, but they call themselves many times and all called are kept in memory until the last called returns a value. – shift66 Dec 20 '11 at 10:29
  • technicaly the function parameters are kept in the call stack for all functions. hence there is no special overhead for the recursive functions. the problem comes from how would one use them. – Deian Sep 25 '12 at 22:05
1

Recursive function is no different than a normal function!

The motivation to use recursive functions vs non-recursive is that the recursive solutions are usually easier to read and comprehend.

one example is Fibonacci numbers function.

WARNING: one needs to consider good exit conditions otherwise a wrong recursion would create a stack overflow exception.

Deian
  • 1,237
  • 15
  • 31
1

Recursion is a clean and clever way of making shorter methods and functions that are easy to read. Java is not much different in dealing with recursion compared to other languages.

Certain applications, like tree search, directory traversing etc. are very well suited for recursion.

The drawbacks are that you may need a little time to learn how to use it and you may need a little longer to debug errors. Recursion could cause memory problems if your iterations are huge.

Costis Aivalis
  • 13,680
  • 3
  • 46
  • 47
0

I only use recursion when it leads to a greatly reduced amount of code. for instance, the classic tree fractal where you would want to generate a tree by drawing smaller and smaller lines. with recursion you can make the code for this a lot faster than most codes that just use loop structures, and since each recursion has local variables, less variables. but that's just my opinion.

Phill McKracken
  • 1
  • 1