Geek Answers Handbook

The relevance of recursion

So, I'm currently trying to understand the concept of recursion, and I understand most of the problems that I have encountered, but I feel that its use will not apply to too many computational problems. This is just a beginner, but I ask, are there many practical uses for recursion as a programmer? And also, what typical problems can be solved with it? The only ones I saw were a bunch of sorting and brain teaser problems like The Towers of Hanoi, which seemed very specific and not widely used.

thanks

+4
source share
7 answers

It depends on what you are going to do, I suppose. I probably write less than one recursive function per year as a C # / ASP.NET developer doing corporate web work. When I screw my code for hobbies (mainly for studying statistics), I find much more possibilities for applying recursion. This is partly due to the fact that I am much more dependent on third-party libraries that the client has already decided when doing corporate work (where algorithms that require recursion are implemented).

+1
source

There are many uses for recursion in programming — a classic example of navigating a tree structure, where you call a navigation function with every child element it finds, etc.

+3
source

Here are some fields that would be nearly impossible without recursion:

  • XML, HTML, or any other tree similar to the structure of a document.
  • Compilation and analysis
  • Natural Language Processing
  • Split and overcome algorithms
  • Many mathematical concepts, for example. factorials

Recursion can lead to brilliant elegant solutions for complex problems. If you are ever interested in programming as an art, you really need to go deeper.

Oh, and if you're not sure, here is a solid definition of recursion:

Recursion (noun): See "Recursion"

+3
source

This is not what you use every day. But many data retrieval and sorting algorithms can use it. In general, most recursive algorithms can also be written using iteration; often a recursive version is easier.

0
source

If you check the questions that are listed as “Related” to this question, you will find “a lot” of recursion things to help you better understand this.

Recursion is not new, and it is not just a toy. Recursive algorithms have existed since computers appeared.

The classic definition of factorial is a prime example:

fact(x) = if x < 0 then fact(x) is undefined if x = 0 then fact(0) = 1 if x > 0 then fact(x) = x * fact(x-1)

This is not something that was created by computer geeks who thought recursion was a cool toy. This is a standard mathematical definition.

0
source

Call recursion, as a program constructor, is something that should almost never be used, except in extremely high-level languages, where you expect the compiler to optimize it for another construct. Using call recursion, unless you can set small boundaries at depth, results in a stack overflow , rather than a nice view that answers your questions for you. :-)

Recursion as an algorithmic concept, on the other hand, is very useful. This is the key to working with any recursively defined data formats (for example, HTML or XML or a hierarchical file system), as well as for implementing important search algorithms, sorting and (all your favorite) graphic images among countless other fields.

0
source

There are several languages ​​that do not support loops (i.e. for and while), and as a result, when you need to repeat the behavior, you need to use recursion (I believe J has no loops). In many examples, recursion requires much less code. For example, I wrote the isPrime method, it took only two lines of code.

public static boolean isPrime(int n) { return n!=1&&isPrime(n,2); }

public static boolean isPrime(int n,int c) { return c==n||n%c!=0&&isPrime(n,c+1); }

An iterative solution will require much more code:

 public static boolean isPrime(int n) { if(n==1) return false; int c=2; while(c!=n) { if(n%c==0) return false; } return true; }

Another good example is working with ListNodes, for example, if you want to check if all the elements in the ListNode are the same, the recursive solution will be much simpler.

 public static <E> boolean allSame(ListNode<E> list) { return list.getNext()==null||list.getValue().equals(list.getNext().getValue())&&allSame(list.getNext()); }

The iterative solution would look something like this:

 public static <E> boolean allSame(ListNode<E> list) { while(list.getNext()!=null) { if(!list.getValue().equals(list)) return false; list=list.getNext(); } return true; }

As you can see, in most cases recursive solutions are shorter than iterative solutions.

0
source

More articles:


All Articles