Recursion in C++

What is Recursion in C++?

When a function is called within another function, it is referred to as recursion. A recursive function calls the same function, while a tail recursion calls itself without performing any tasks after the call. In tail recursion, the same function is typically called with the return statement.

Recursive function

Recursive functions are defined as functions that call themselves. When a recursive function is invoked, it runs a sequence of instructions before calling itself to repeat the process with a smaller input. This process continues until it reaches a base case, which is a condition that terminates the recursion and returns a value.

Base Condition

The base condition is the condition that causes the recursion to terminate. The recursive function will repeatedly call itself until the basic condition is met.

Recursive Case

The recursive case describes how the recursive call appears in the code. The recursive case can include numerous recursive calls or varied parameters so that the base condition is satisfied and the recursion is terminated.

How Recursion Works in C++?

• Recursion occurs when a function calls itself to solve smaller instances of the same problem.
• The function has a base case that ends recursive calls, preventing infinite loops.
• In the absence of the base case, the function executes a recursive step to reduce the size of the problem.
• Each recursive call saves its execution context to the call stack until the base case is reached.
• When the base case is met, the call stack unwinds and returns values from before calls to deliver the final result.

C++ Recursion Types

There are two types of recursion, as follows:

1. Direct recursion
2. Indirect recursion

Direct Recursion

Direct recursion occurs when a function contains one or more recursive calls to itself. In direct recursion, the function calls itself directly, with no intervening functions. Direct recursion can also be categorized into three types based on the number of recursive calls in the function's body.

Head Recursion

In head recursion, the recursive call occurs at the beginning of the function. It is a type of linear recursion in which just one recursive call is made.

Tail Recursion

Tail recursion is a linear recursion in which a single recursive call occurs at the end of the function. The recursive call is usually the last statement in the function. The significance of tail recursion lies in the fact that we can use tail call optimization to reduce memory consumption.

Tree Recursion

The function's body contains many recursive calls. Tracing tree recursion yields a tree-like structure with numerous recursive calls branching from a single function.

Indirect recursion

When a function uses indirect recursion, it calls another function first, which in turn calls the original function, generating a cycle of function calls.

Applications of Recursion in C++

• Solving: Fibonacci sequences, Factorial Function, array reversal, Tower of Hanoi.
• Backtracking: A problem-solving technique that involves attempting several approaches and undoing them if they don't work. Commonly used in recursive algorithms.
• Searching and Sorting Algorithms: Binary search and quicksort use recursion to divide issues into smaller sub-problems.
• Tree and Graph Traversal: For traversing trees and graphs, recursive methods such as depth-first search and breadth-first search are crucial.
• Mathematical Computations: Recursion is used in a variety of mathematical computations, including factorials and Fibonacci sequences.
• Dynamic Programming: This technique divides optimization problems into smaller sub-problems and frequently uses recursive algorithms for efficiency.

Advantages of Recursion

• Recursion can help to reduce the length of the code.
• It provides a clean and straightforward technique for developing code.
• It reduces the need to call the function many times.
• Recursion is advised for issues such as tree traversal and the Tower of Hanoi.

Disadvantages of Recursion

• Recursive functions are slower than nonrecursive ones.
• The code is tough to read and grasp.
• Debugging can be more challenging than in iterative programs.
• It requires more space than iterative programs.
• Due to function calls, it takes more time than usual.