[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 432
  • Last Modified:

What is a linear recursion? What is a binary recursion? What is a tail recursion? How to improve recursion?

just like the title,
-What is a linear recursion?
-What is a binary recursion?  
-What is a tail recursion?
-How to improve recursion?
-What are the pros and cons of using recursion?  

 I don't understand quite well on these topics.
0
jiwonman
Asked:
jiwonman
1 Solution
 
harfangCommented:
Linear recursion means that a function calls itself at most one time. The stack grows linearly; the algorithm never explores several branches at once.

Binary recursion means that a function makes at most two recursive calls. For example for exploring a binary tree: look left and look right.

Tail recursion mens that the recursive call occurs at the end of the function, when all the local work is done. This type of function can often be rewritten more tightly and more efficiently as a non-recursive loop.

Improving recursion in terms of optimization means often to get rid if it. It can also mean to reduce the amount of stack space needed for each iteration, or use forward-looking techniques to reduce the number of recursive calls. Finally, it can mean to avoid exploring several branches simultaneously.

The advantages of using recursion include: clean code, efficient way to traverse a hierarchy or a tree, ease of maintenance, adaptiveness.

The cons are: there often exist faster algorithms, you can easily fill your stack space, it's difficult to debug and detect cyclic bugs, there can be an exponential efficiency loss with growing data structures.

See also
http://en.wikipedia.org/wiki/Recursion
http://en.wikipedia.org/wiki/Tail_recursion

Does that help?
(°v°)
0

Featured Post

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now