Help !! I need a simple definition. What is Recursion ?

Question

Help !! I need a simple definition. What is Recursion ?

Answer 1

Recursion is what happens when a function calls itself from within itself.



There must be a test within the function to determine whether or not the function is finished, in which case it returns a value - either to where it left off from the previous call to itself, or to the routine or program that called it in the first place.



Checking for prime numbers is a good example of the use of a recursive routine.



Recursion isn't good all the time, but when you need to do the same thing to a partial answer, it is valuable. Except it is very difficult to implement safely.



Here is an example of recursion in this web site:

Answer 2

The idea is to keep breaking the list down into smaller bits until there are only one or two elements in the list: Here is some 'pseudocode' that will accomplish this when I write a(i), you should think of this as a sub i. function findmin(a,start, end, min) ' ' function returns the minimum (min) of the ' subset of the list a starting with element 'start' ' and ending with element 'end' ' ' if list has one element, we are done ' if start = end then min = a(start) exit end if ' ' if list has two elements, find which is smaller ' and return that ' if end = start + 1 then min = a(start) 'maybe its the first one? if a(start) > a(end) then min = a(end) 'if not its the 2nd one exit end if ' ' list is too big, lets divide and conquer ' ' get midpoint of list rounded to an integer ' midpoint = int((start+end))/2) ' ' find min of 1st half of list ' findmin(a,start,midpoint,min1) ' ' find min of 2nd half of list ' findmin(a,midpoint+1,end,min2) ' ' figure out which minimum is smaller and return it ' min = min1 'maybe its the first minimum if min1 > min2 then min = min2 'or maybe its the 2nd one exit end function

Answer 3

Recursion is the repeated invocation of a method or procedure, and in programming, it is typically done by having a method/function call itself. For example, you could have a method that walks through a directory structure printing each file that it finds and recursively stepping through each child subdirectory. In the Java language, it might look like:



void walkDirectory(File dir)

{

for (File child : dir.listFiles()) // for each child file

{

System.out.println(child.getName()); // print its name

if (child.isDirectory()) walkDirectory(child); // recursive call

}

}

Answer 4

A recursion is just a bit of code that will run forever.



while ( 1 ) {

do_something;

}



It can be used in deamon programs to keep a paticular bit of code running forever.

Answer 5

to the best of my knowledge, its essentially a loop. can also be an infinite loop.

Answer 6

Recursion literally is using yourself to define yourself.



That probably makes god the ultimate recursion, if he said "I am that I am". :D



But seriously in programing many times the nature of processing a task can be expressed recursively in a better way than procedurally.



Recursive functions or programs often behave on lists of data, for instance, if you have a list of names like this:



Jack, James, Jeff, ...



You might need to process the list to determine if there is a "girls" name in the list.



As you read the question, you probably Thought it was trivial, only three names, but even with this list of 10, your mind will look at each one, and decide "is this a boy's name or girl's name?" If it's a boy's name you continue to the next name in the list:



Jack, James, Jeff, Jerry, Jimmy, Jill, Joe, John, Jules, Julio



Even with 10 you recursively read the names one at a time until you hit "Jill".



What if there were thousands of names. The procedure is the same even if we might die of boredom executing it.



So a recursive description of the name problem:



Determine if a list of names contains a female name.



A) with a list of names, examine the first name.

B) Is the name Female? Then answer "Yes"

C) If not, are there anymore names in the list? If not then answer "No"

D) create a list from the remaining names and pass the new list back to A).



Do you see the recursion? the Process, uses the "process" to define itself.



Unfortunately, the truth is recursion is often a difficult concept to grasp, and even if you do get it, there are always non-recursive solutions to the same problems. But recursion does serve a purpose because some types of problems are easier to solve in a recursive manner.



Good Luck