You must specify a subject when posting a new topic.

Home Forums C Programming You must specify a subject when posting a new topic.

This topic contains 1 reply, has 2 voices, and was last updated by  Adetutu 9 years, 7 months ago.

  • Author
  • #2100


    Detail About Recursion and its Type

    Here I am going to give a detail about Recursion in C++.
    Definition: Recursion is the process where a function is called itself but stack frame will be out of limit because function call will be infinite times. So a termination condition is mandatory to a recursion.
    In C++, Recursion can be divided into two types:

    1. Run- Time Recursion: Normal as in C
    2. Compile- Time Recursion: By using Template

    Each of these can be also divided into following types:

    1. Linear Recursion
    2. Binary Recursion
    3. Tail Recursion
    4. Mutual Recursion
    5. Nested Recursion

    1. Linear Recursion: This recursion is the most commonly used. In this recursion a function call itself in a simple manner and by termination condition it terminates. This process called ‘Winding’ and when it returns to caller that is called ‘Un-Winding’. Termination condition also known as Base condition.

    Example: Factorial calculation by linear recursion
    Run-Time Version

    Winding Process:
    Function return

    Fact(6) 6*Fact(5)
    Fact(5) 5*Fact(4)
    Fact(4) 4*Fact(3)
    Fact(3) 3* Fact(2)
    Fact(2) 2* Fact(1)
    Fact(1) 1* Fact(0)

    Terminating Point
    Fact(0) 1

    Unwinding Process

    Fact(1) 1*1
    Fact(2) 2*1
    Fact(3) 3*2*1
    Fact(4) 4*3*2*1
    Fact(5) 5*4*3*2*1
    Fact(6) 6*5*4*3*2*1

    Compile-Time Version

    To test it how it’s working at compile time, just call

    And compile it then compiler error will come, because no template for -1.

    2. Binary Recursion: Binary Recursion is a process where function is called twice at a time inplace of once at a time. Mostly it’s using in data structure like operations for tree as traversal, finding height, merging, etc.

    Example: Fibonacci number

    Run Time Version Code:

    Compile Time Version Code

    3. Tail Recursion: In this method, recursive function is called at the last. So it’s more efficient than linear recursion method. Means you can say termination point will come(100%) only you have to put that condition.

    Example: Fibonacci number

    Run Time Version Code:

    Compile Time Version Code

    4. Mutual Recursion: Functions calling each other. Let’s say FunA calling FunB and FunB calling FunA recursively. This is not actually not recursive but it’s doing same as recursive. So you can say Programming languages which are not supporting recursive calls, mutual recursion can be applied there to fulfill the requirement of recursion. Base condition can be applied to any into one or more than one or all functions.

    Example: To find Even Or Odd number

    Run Time Version Code:

    Compile Time Version Code

    3. Nested Recursion: It’s very different than all recursions. All recursion can be converted to iterative (loop) except nested recursion. You can understand this recursion by example of Ackermann function.

    Example: Ackermann function

    Run Time Version Code:

    Compile Time Version Code

  • #3388


    Thanks buddy. I have used all the methods but was not aware about these terms.

You must be logged in to reply to this topic.