• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • Devaka Cooray
  • Ron McLeod
  • Jeanne Boyarsky
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Martijn Verburg
  • Frits Walraven
  • Himai Minh

Recursive Functions

 
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Is it the right way to use recursive funtions?

If not what is the alternate?
 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
On scenario's where it is usefull to use recusion it is mostly the best option.
Just make sure your code stays a bit readable.
 
Rancher
Posts: 43028
76
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There's nothing wrong with recursive algorithms per se. They tend to be shorter, and look more elegant when implemented, although that can be deceiving.

One example are the Fibonacci numbers. They are usually defined recursively, and very easy to implement that way. But the recursive approach has exponential complexity, while it's easy to implement an iterative approach that has linear complexity.

So the answer is, it depends. They're neither always faster, nor always slower, than comparable non-recursive algorithms. I'm mentioning this because I've seen both opinions stated numerous times, and they're simply not true.
[ February 20, 2008: Message edited by: Ulf Dittmer ]
 
Marshal
Posts: 76885
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The problem with recursion is that it can be hungry on memory; I find on my PC that recursions which get out of hand cause a StackOverflowError somewhere between 3000 and 4000 calls. But recursion done correctly is a nice technique, as Ulf has told us.

But I know how to write a Fibonacci recursion which runs in linear time, and if you look in Anne Kaldewaij's book Programming : the derivation of algorithms Hemel Hempstead : Prentice Hall International, 1990, I think page 98, you can find how to write a Fibonacci number which runs in logarithmic time.

The alternative to recursion is iteration, which in Java means while, do-while or for.
 
I once met a man from Nantucket. He had a tiny ad
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic