A Simple Introduction to Recursion

Board Infinity
Board Infinity
A Simple Introduction to Recursion

    Data Structures: Foundation of Effective Programming

    10 Common Data Structures Every Programmer Must Know

    Quick Guide to Abstract Data Types

    A Simple Introduction to Recursion

    Arrays vs Linked List

    Stack in Data Structure

    Complete Walkthrough of Stacks in Data Structure

    Working on Queue using STL

    Implementing Queue using Stacks

    A Detailed walkthrough of the Doubly Linked List

    How to Reverse a Linked List?

    Binary Tree Code Implementation

    Complete Walkthrough of AVL Trees

    Heap Data Structure

    Trie Data Structure: Explanation and Examples

Introduction

Recursion is a C++ method that calls itself repeatedly until a certain condition is met. This technique has a base case and a recursive condition, calling the same function repeatedly. Recursive conditions help repeat code over and over, and base cases help terminate conditions.

Implementation

Recursion can be used to solve almost any problem, and sometimes it really helps. It is generally used when dealing with complex problems or problems that form hierarchical patterns. Solve the original problem through smaller sub-problems.

void recurse()

{

    ... .. ...

    recurse();

    ... .. ...

}


int main()

{

    ... .. ...

    recurse();

    ... .. ...

}

Developers should pay close attention to recursion. Because it's easy to write functions that never terminate, or consume excessive memory or processing power. However, if written correctly, recursion can be a very efficient and mathematically elegant programming approach.

Recursion consumes more memory because recursive functions add something to the stack for each recursive call and retain the value until the call completes. Recursive functions use a LIFO (LAST IN FIRST OUT) structure as well as a stack data structure.

Example 1: Calculating Factorial

// Factorial of n = 1*2*3*...*n


#include <iostream>

using namespace std;


int factorial(int);


int main() {

    int n, result;


    cout << "Enter a non-negative number: ";

    cin >> n;


    result = factorial(n);

    cout << "Factorial of " << n << " = " << result;

    return 0;

}


int factorial(int n) {

    if (n > 1) {

        return n * factorial(n - 1);

    } else {

        return 1;

    }

}



write your code here: Coding Playground

Output:

Enter a non-negative number: 4

Factorial of 4 = 24

Advantages of  Recursion

  • This makes your code shorter and cleaner.
  • Recursion is necessary for problems involving data structures and sophisticated algorithms such as graph and tree traversals.

Disadvantages of  Recursion

  • It takes up a lot of stack space compared to iterative programs.
  • Consume more processor time.
  • It can be more challenging to debug compared to equivalent iterative programs.