Recursion

• Recursion

Java #20 - Recursion Part 1
http://www.youtube.com/watch?v=Bu0X20xOxIs&feature=channel&list=UL

• Java #21 - Recursion Part 2

http://www.youtube.com/watch?v=Mo59NNK8POE&feature=autoplay&list=ULBu0X20xOxIs&lf=channel&playnext=1

• Fibonacci Series

http://www.java-examples.com/fibonacci-series-java-example

• Example-Fibonacci Numbers

http://www.brpreiss.com/books/opus5/html/page75.html

• Fibonacci numbers (Java)

http://en.literateprograms.org/Fibonacci_numbers_%28Java%29

• What are advantages and disadvantages of recursive calling ?

Through Recursion one can Solve problems in easy way while
its iterative solution is very big and complex.
Ex : tower of Hanoi
You reduce size of the code when you use recursive call.

Disadvantages :
Recursive solution is always logical and it is very
difficult to trace.(debug and understand)


Recursive procedures are huge memory hogs. Also, they're a nightmare to debug. Finally, it's pretty rare to find an application that actually needs recursion as opposed to a simpler, more friendly methodolgy.

Read more: http://wiki.answers.com/Q/What_are_the_disadvantages_of_recursion#ixzz1xDJz1EG4

• Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually simplicity. The main disadvantage is often that the algorithm may require large amounts of memory if the depth of the recursion is very large.

http://en.wikipedia.org/wiki/Recursion

• Advantages

Although at most of the times a problem can be solved without recursion, but in some situations in programming, it is a must to use recursion. For example, a program to display a list of all files of the system cannot be solved without recursion.
The recursion is very flexible in data structure like stacks, queues, linked list and quick sort.
Using recursion, the length of the program can be reduced.

Disadvantages

It requires extra storage space. The recursive calls and automatic variables are stored on the stack. For every recursive calls separate memory is allocated to automatic variables with the same name.
If the programmer forgets to specify the exit condition in the recursive function, the program will execute out of memory. In such a situation user has to press Ctrl+ break to pause and stop the function.
The recursion function is not efficient in execution speed and time.
If possible, try to solve a problem with iteration instead of recursion

http://my.safaribooksonline.com/book/programming/c/9788131760314/functions/section_10.20

• Rule of the thumb: use recursion when it will shorten your development effort (usually in tree structures) and when performance is not an issue.

Recursive functions are perfect for tree structures. Loops are perfect for iterations and sequences.

public List GetAllFilesInTree(string path)
{
    List files = new List(GetAllFilesInFolder(path));
    foreach (string subdir in GetAllFoldersInFolder(path))
    {
        files.AddRange(GetAllFilesInTree(path));
    }
}



Advantages of Recursion
The code may be much easier to write.
Some situations are naturally recursive.


Naturally recursive data structures:
Linked lists.
Binary trees.

Naturally recursive problems:
Traversing linked lists.
Traversing binary trees.
Evaluating expressions.
Differentiating functions.
The Triangle puzzle.


Disadvantages of Recursion
Recursive functions are generally slower than
nonrecursive functions.
Excessive recursion may over?ow the run-time stack.
One must be very careful when writing recursive
functions; they can be tricky.
There is shallow recursion and there is deep recursion.
Shallow recursion will not over?ow the stack, but it may
take an excessively long time to execute.
Deep recursion is generally much faster, but it may
over?ow the stack.

The time and space overhead used by the stack on each call is a disadvantage of recursion. You should always minimize the number and size of the recursive function's arguments.

• Recursion

Recursion means "defining a problem in terms of itself".
This can be a very powerful tool in writing algorithms.
Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves
http://www.cs.utah.edu/~germain/PPS/Topics/recursion.html

• A brute force algorithm

A brute force algorithm attempts to check systematically all possible keys until the correct one has been found.
In the worst case the algorithm has to check each available combination in order to find the correct key.
https://janosch.woschitz.org/a-simple-brute-force-algorithm-in-c-sharp/

Finding a Brute Force Solution

• Recursive Backtracking

A brute force algorithm is a simple but general approach
Try all combinations until you find one that works
This approach isn’t clever, but computers are fast
Then try and improve on the brute force resuts
http://www.cs.utexas.edu/~scottm/cs314/handouts/slides/Topic13RecursiveBacktracking_4Up.pdf