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

Posted on 2009-02-17
Last Modified: 2012-05-06
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.
Question by:jiwonman
    1 Comment
    LVL 58

    Accepted Solution

    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

    Does that help?

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Better Security Awareness With Threat Intelligence

    See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

    Suggested Solutions

    Title # Comments Views Activity
    withoutString  challenge 40 119
    only14 challenge 19 57
    bunnyEars challenge 6 45
    Python 2.7 - French characters 6 28
    Introduction A frequently used term in Object-Oriented design is "SOLID" which is a mnemonic acronym that covers five principles of OO design.  These principles do not stand alone; there is interplay among them.  And they are not laws, merely princ…
    Having just graduated from college and entered the workforce, I don’t find myself always using the tools and programs I grew accustomed to over the past four years. However, there is one program I continually find myself reverting back to…R.   So …
    The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
    This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.

    760 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    15 Experts available now in Live!

    Get 1:1 Help Now