• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursion  RSS feed

 
nicky priya
Greenhorn
Posts: 28
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Hi everyone. What is Recursion and how it is used and what is the use of it. Can anyone please explain me in simple words with an simple example.
 
Paweł Baczyński
Bartender
Posts: 2083
44
Firefox Browser IntelliJ IDE Java Linux Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think this is a good explanation.
Wikipedia simple English wrote:A recursive algorithm is a function that tells itself to do something, resulting in it running over and over on smaller and smaller inputs. At the end, it gives back a value.


A "classic" example is factorial. The code may look like this:
 
nicky priya
Greenhorn
Posts: 28
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Thank you for replying.
I have understood the simple factorial example but why should we use always give factorial example.
Is there any possibility of any other example.
 
Liutauras Vilda
Sheriff
Posts: 4921
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursion, or let's speak specifically about recursive method here. Well, it is a method, which calls itself at some point.

i.e.:

Now, recursion has two main parts:
[1] stopping condition or base case, what you see on line 2 in the code example, where (in simple words) there is no other recursive call
[2] and the condition when method calling itself until reaches stopping condition. In order to reach stopping condition, argument passed to a recursively called method need to be different (smaller or higher value) based on the condition you have defined as a stopping one.

In Java there isn't much use of it in real world applications as it is considered to be an unreliable way of solving problems, because it relies on the size of input and at some point stack overflows due to lack of memory. But that is due of Java programming language nature (think just like that for moment, if interested read about tail recursion for more info).

Functional languages usually prefer recursion over iteration, for various reasons.
 
nicky priya
Greenhorn
Posts: 28
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Okay Thank you.
 
Carey Brown
Saloon Keeper
Posts: 3323
46
Eclipse IDE Firefox Browser Java MySQL Database VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Paweł Baczyński wrote:I think this is a good explanation.
"Wikipedia simple English" wrote:A recursive algorithm is a function that tells itself to do something, resulting in it running over and over on smaller and smaller inputs. At the end, it gives back a value.


A "classic" example is factorial. The code may look like this:

Yes, this is the "classic" example, but it can be easily converted from recursion to iterative.
One of the potential problems with recursion is the possibility of running out of stack space.

The recursive example I prefer is tree traversal. A directory hierarchy is a well known example of a tree structure. So to traverse the tree, recursion is our best choice because at any node of the tree we don't know how many children it has or how deep it will go.
 
Junilu Lacar
Sheriff
Posts: 11493
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
nicky priya wrote:why should we use always give factorial example.
Is there any possibility of any other example.

You said it yourself, it's an example that's easy to understand. If you want to find other examples, you can always search:
Other examples of recursive algorithms

Others I can think of that have been discussed here at one time or another:
Fibonnaci Fibonacci series, largest/smallest number in an array, Tower of Hanoi puzzle.

You might also want to check out the list of related topics at the bottom of this page.
 
Naziru Gelajo
Ranch Hand
Posts: 175
1
Java Netbeans IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Recursion is when you use a method to call itself in the same method (direct recursion). Have you ever studied induction in Discrete mathematics? it's a similar concept. Factorial is a perfect example of recursion.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!