• Post Reply Bookmark Topic Watch Topic
  • New Topic

recursive functions  RSS feed

 
felix thomas
Ranch Hand
Posts: 89
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi,

I want to know what is the basic advantage of using recursive functions
 
Jeroen Wenting
Ranch Hand
Posts: 5093
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
demonstrating stack overflow in programming courses comes to mind

Seriously, there are times when the solution of a problem is best defined by means of an operation that as part of its algorithm performs itself.
 
Peter Rooke
Ranch Hand
Posts: 900
7
Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Compare these two different way to compute factorials:

1) Without recursion, this method [written in Java]:


2) With recursion, this [written in ML]:

Of course these are two completely different programming languages, but you get the idea; the recursive version is a more natural way to think .
Of course you can re-write the recursive version in Java, but I've always liked the look of functional languages. Never quite understood some of the mind boggling stuff (like - prolog :eek .

Recursion: see recursion
(Could not resist that one )

[ January 06, 2005: Message edited by: Peter Rooke ]
[ January 06, 2005: Message edited by: Peter Rooke ]
 
Mike Gershman
Ranch Hand
Posts: 1272
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Many mathematical functions like factorial and fibonacci progressions and many algorithms like quicksort and depth-first-search are defined recursively, so it's natural to write recursive code when efficency is not an issue.

You can always convert these programs into conventional loops to save CPU cycles and memory, but any such translation can introduce subtle errors if you're not careful.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursion is handy when processing trees, say file system directories. I might call a method to list a directory, and when it finds a subdirectory it calls itself to list that one, too.

Trees are often loaded into memory as a series of nodes that have 0..many child nodes. If you look at a node to do some processing you might decide to process the children after processing the node itself or maybe before. XML parsers generate trees like this and recursive processing is common.

I use recursion to handle text replacement macros. A macro like ${linksto ${page}} returns a list of pages that link to the current page. The routine finds the first "${linksto" and gets the data up to the matching end bracket. Then it calls itself to examine the stuff inside the brackets for more macros and finds ${page}. It replaces ${page} with the page name, and returns to itself to process ${linksto thename}.

All of these are some form of nested data. If you see recursive data structures you're likely to see recursive solutions.
 
felix thomas
Ranch Hand
Posts: 89
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
thanx guys
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!