How often do you use recursion?

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 4868 Views - Last Post: 27 December 2011 - 10:10 AM

#1 Codebug  Icon User is offline

  • D.I.C Head

Reputation: 31
  • View blog
  • Posts: 244
  • Joined: 11-October 09

How often do you use recursion?

Posted 07 April 2010 - 01:21 PM

I was just wondering how often you guys use recursion. Whether you program for a living or program for a hobby, how often do you implement recursive solutions? I've only recently been introduced to recursion and while I don't find the recursive concept to be difficult to understand, I have been having problems following recursive code and developing recursive solutions to problems. I know it is useful for a wide variety of applications. I'm just trying to see whether most of you guys use it or not. Also, I would be very grateful if you guys could provide a link or two to some resources that could help break down the recursive process.

Thanks

Is This A Good Question/Topic? 0
  • +

Replies To: How often do you use recursion?

#2 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 337
  • View blog
  • Posts: 729
  • Joined: 27-June 09

Re: How often do you use recursion?

Posted 07 April 2010 - 03:45 PM

I use recursion fairly often. I'm not really certain there is one recursive process that can be broken down for you. Rather, there are situations where recursion is far better than looping. Traversing trees and divide & conquer algorithms are a few examples that come to mind. For following recursive code, I often find it best to decode the algorithms by reading the recursive calls as the results they are supposed to return and not think too much about what happens in the call. Take the binary sort for example.
bSort(int a, int b, arr) //sorts elements in arr between position a and position b
{
check for terminating condition
choose pivot element
move elements less than pivot between a and mid
move elements greater than pivot between mid and b
/***By this point, all elements before mid are less than the pivot element, and all elements after mid are greater than pivot element***/
bSort(a, mid-1, arr) //read this as "sorting all elements before mid"
bSort(mid+1, b, arr) //read this as "sorting all elements after mid"
put pivot element at mid //pivot goes in the middle
//the array is now sorted from a to b
}



Doing this wont help in all recursive solutions, but it simplified many problems for me. Hope that helps.
Was This Post Helpful? 1
  • +
  • -

#3 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 610
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: How often do you use recursion?

Posted 07 April 2010 - 07:18 PM

Well, a lot of functional programming languages (a la Haskell) don't even have traditional loop structures. They don't make sense in purely functional languages, but occasionally make sense in impure functional languages.

For the languages I've used, the idea went like this: Use collection/sequence/list functions to abstract over the recursion for you when possible, and if that isn't possible use recursion.

For example, one could write a reverse function in Clojure like this:

(defn my-reverse 
  ([[x & more] acc] (if (seq more) (recur more (conj acc x)) (conj acc x)))
  ([coll] (my-reverse coll '())))



This example uses tail recursion. It's rather easy to follow for Clojure programmers (and probably FPers in general), but that doesn't always hold true. You can also define that same function like this (defn my-reverse2 [coll] (reduce conj '() coll)). Now isn't that more readable? Reduce does the recursion for us. This is the idiomatic way to write any recursive function. If there is a clean way to do it otherwise, explicit recursion probably isn't the best way to do something.

Loop structures are used less than recursion, and recursion is used less than sequence functions in FP languages. Doing this leads to cleaner and safer solutions than mutating some variable from within a for loop.

So, my answer to your question is "Not really.". Even as an FPer, I don't use recursion nearly as much as you might expect. In most cases, there is a way to do what you want just using sequence functions, or a list comprehension, and sometimes a loop structure leads to a cleaner solution.
Was This Post Helpful? 0
  • +
  • -

#4 MentalFloss  Icon User is offline

  • "ADDICTED"[2:5]
  • member icon

Reputation: 525
  • View blog
  • Posts: 1,397
  • Joined: 02-September 09

Re: How often do you use recursion?

Posted 07 April 2010 - 11:30 PM

The only time I have found to use recursion where it made real sense is traversing trees - specifically the TreeView control in C#.

As an academic exercise, the only thing that comes to mind to elegantly be solved with recursion is the Fibonacci sequence. Who ever has to really do that though?

So, once or twice. I'm not professional either so there is that to consider. Maybe it comes up much more often in the real world. I doubt it though.
Was This Post Helpful? 0
  • +
  • -

#5 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 610
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: How often do you use recursion?

Posted 08 April 2010 - 12:17 AM

Well, there are all sorts of stuff that is solved elegantly with recursion. http://rosettacode.o...Towers_of_Hanoi is another example. The point of my post is that in less functional languages, recursion isn't always very idiomatic. In languages without tail-call optimization (Python), it's also dangerous and unpredictable for large collections and such.

funfact: Clojure doesn't actually have TCO (tail-call optimization) because the JVM doesn't support it, but instead uses the 'recur' special form to achieve the same effect. (Just in case somebody has read "Clojure doesn't have TCO." and is like lolwut.)
Was This Post Helpful? 0
  • +
  • -

#6 111027  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 141
  • Joined: 26-December 11

Re: How often do you use recursion?

Posted 26 December 2011 - 10:55 AM

No more often than i use recursion.

Now seriously :) I rarely use recursion in the algorithms i develop. I mainly use it to traverse some data structures, but most of my solutions tend to be iterative ones - in my line of programming, the overhead would kill me.
Was This Post Helpful? 1
  • +
  • -

#7 wordswords  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 76
  • View blog
  • Posts: 272
  • Joined: 17-December 11

Re: How often do you use recursion?

Posted 26 December 2011 - 11:30 AM

I used to use recursion a lot at university. Since half my major was Artificial Intelligence, I used recursion for search algorithms like breadth first search, depth first search, A*, prolog and tree traversal algorithms.

However in the 'real world' I almost never have had to directly use recursion. I am sure I've used libraries and other language features that use recursion though, so it is definitely worth getting a strong understanding of it.
Was This Post Helpful? 0
  • +
  • -

#8 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 610
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: How often do you use recursion?

Posted 26 December 2011 - 11:59 AM

Right, that's the idea. Recursion is a fantastic tool for elegantly solving lots of problems. However, one rarely has to actually use it himself. A good language provides abstractions over common recursive idioms so that you don't have to duplicate code for similar problems. The primary examples of this are filter, reduce (folds in Haskell), and map, among others.
Was This Post Helpful? 0
  • +
  • -

#9 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,352
  • Joined: 29-May 08

Re: How often do you use recursion?

Posted 26 December 2011 - 12:12 PM

The programming language Nemerle only as recursion. All the looping constructs (if fact are macros) that translate them into recursive one.

Blog Post Entry: Loopy Abstract Thinking
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,594
  • Joined: 27-December 08

Re: How often do you use recursion?

Posted 26 December 2011 - 12:13 PM

Quote

The programming language Nemerle only as recursion.

Erlang is the same way. It doesn't have loops. Iteration is accomplished with recursive calls.
Was This Post Helpful? 0
  • +
  • -

#11 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,352
  • Joined: 29-May 08

Re: How often do you use recursion?

Posted 26 December 2011 - 12:26 PM

Recursion is used often over lists.


Sum ( l : NList[int], total : int = 0 ) : int 
{ match (l) Head :: Tail 
  { |   []    => total;
    | _ :: _  => Sum( l.Tail, total + l.Head )
  }
}

Was This Post Helpful? 0
  • +
  • -

#12 Raynes  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 610
  • View blog
  • Posts: 2,815
  • Joined: 05-January 09

Re: How often do you use recursion?

Posted 26 December 2011 - 01:45 PM

Clojure is similar. It has one primary looping structure, but that it is essentially isolated recursion.

(loop [x 0]
  (if (< x 5)
    (recur (inc x))
    x))



There is also a 'while' loop that is basically what you'd expect, but is never used in real code because it really just doesn't make sense in a functional language. Hell, it's never used in fake code...
Was This Post Helpful? 2
  • +
  • -

#13 111027  Icon User is offline

  • D.I.C Head

Reputation: 17
  • View blog
  • Posts: 141
  • Joined: 26-December 11

Re: How often do you use recursion?

Posted 26 December 2011 - 02:22 PM

And C++ offers all of the above. Kudos on me :)

Seriously now, recursion can be either a very good thing or a very bad thing. But i'd say it depends on the situation and the programmer.
Was This Post Helpful? 0
  • +
  • -

#14 anonymouscodder  Icon User is offline

  • member icon

Reputation: 126
  • View blog
  • Posts: 710
  • Joined: 01-January 10

Re: How often do you use recursion?

Posted 26 December 2011 - 08:12 PM

Almost never out of academic enviroment.

For example there was some text manipulation that a coworker wrote using recursion, I spent more time checking up what exactly it was doing than finding out a regex alternative.
Was This Post Helpful? 0
  • +
  • -

#15 stackoverflow  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 164
  • View blog
  • Posts: 545
  • Joined: 06-July 11

Re: How often do you use recursion?

Posted 26 December 2011 - 09:52 PM

Dynamic programming techniques often destroy recursive solutions, performance wise.

This post has been edited by stackoverflow: 26 December 2011 - 09:52 PM

Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2