Recursion is very useful in solving certain problems

Recursion

When a function calls itself, it is called recursion. Recursion can be direct or indirect. Recursion is very useful in solving certain problems that are difficult to solve using iterative methods. Tower of Hanoi is a very famous problem that is solved using recursion.

Base Condition

While solving problems with recursion, the original problem is broken up into smaller problem until a smallest unit of problem hits which is directly solvable. This smallest unit is called base condition. The solution to base case is provided and is used to get the solution of the original problem.
Let’s see an exmple

int factorial(int n)
{
    if (n == 1) // base case
        return 1;
    else    
        return n*factorial(n-1);    
}

In the above example, base case for (n == 1) is defined and larger value of number can be solved by converting to smaller one till base case is reached. The above program returns the factorial of the given number.

Base condition is very important and should be defined carefully. If not defined properly, recursion may never stop and overflow can occur.

Direct/Indirect Recursion

Simply put, when a function continuously calls itself it is called direct recursion and when a function calls some other function continuously it is called indirect recursion.
Let’s see some examples

// An example of direct recursion
void foo()
{
    //something 
    foo();
    // Some code...
}
// An example of indirect recursion
void foo()
{
    // Some code...
    bar();
    // Some code..
}
void bar()
{
    // Some code...
    foo();
    // Some code...
}

Memory allocation for recursion

Whenever any function is called, memory for that function call is allocated on stack memory. The memory for called function is allocated on top of stack and copies of local variable are created for that function.
When the base case is reached and the execution of that particular function is over, the control is passed to the calling function and memory for the called function is popped off the stack i.e. the memory is deallocated.

Program for Recursion

#include<bits/stdc++.h>
using namespace std;
 
void Fun(int t)
{
    if (t < 1)
        return;
    else
    {
        cout << t << " ";
        Fun(t-1);    
        cout << t << " ";
        return;
    }
}
 
int main()
{
    int t = 3;
    Fun(t);
}

Output

3 2 1 1 2 3
When Fun(3) is called from main(), memory is allocated to Fun(3) and a local variable test is initialized to 3 and statement 1 to 4 are pushed on the stack. It first prints 3. In statement 2, Fun(2) is called and memory is allocated to Fun(2) and a local variable test is initialized to 2 and statement 1 to 4 are pushed in the stack. Similarly, Fun(2) calls Fun(1) and Fun(1) calls Fun(0). Fun(0) goes to if statement and it return to Fun(1). Remaining statements of Fun(1) are executed and it returns to Fun(2) and so on. In the output, value from 3 to 1 are printed and then 1 to 3 are printed.

AUTHOR

READ NEXT

Boostlog is an online community for developers
who want to share ideas and grow each other.

Delete an article

Deleted articles are gone forever. Are you sure?