Last updated on September 4th, 2023 at 09:48 pm

Here, We will learn about recursive algorithm, recursion, recursive function, implementation, properties and examples of recursion.

**Recursive Algorithms:**

A **Recursive Algorithm** that calls itself repeatedly until a base condition is satisfied. **Recursion** is a technique in which function calls itself.

A recursive method that solves a problem by calling a copy of itself to work on a smaller problem is called a **recursion step.**

A **Recursive function** performs a task in part by calling itself to perform the subtasks. Recursive code is generally shorter and easier to write than iterative code.

```
public static long fib (long n)
{
if (n <= 1)
return n;
else
return fib (n-1) + fib (n-2);
```

Code language: Java (java)

**Recursion** is most useful for tasks that can be defined in terms of similar sub-tasks. **For example,** Sort, Search and traversal problems have simple recursive solutions.

Each recursive algorithm has at least 2 cases :

**Recursive Case:**a conditional statement that is used to trigger the recursion.**Base Case:**a conditional statement that is used to break the recursion

Every recursive case must eventually lead to a base case

**Properties of Recursion**

- The recursive solution is less efficient than the iterative solution due to the overhead of function calls
- It uses a selection structure.
- It is usually slower than iteration due to overhead of maintaining stack
- It uses more memory than iteration.
- It makes code smaller.
- Infinite recursion can crash the system.

**Examples of Recursive Algorithm**

- Fibonacci Series, Factorial Finding
- Merge Sort, Quick Sort
- Binary Search
- Tree Traversals: InOrder, PreOrder and PostOrder
- Graph Traversals: DFS (Depth First Search) and BFS (Breadth First Search)
- Divide and Conquer Algorithms
- Tower of Hanoi
- Dynamic Programming Examples
- Backtracking Algorithms

### Related:

*Want to Contribute*:-

If you like “**To The Innovation**” and want to contribute, you can mail your articles to ðŸ“§ **contribute@totheinnovation.com**. See your articles on the main page and help other coders.ðŸ˜Ž