A Complete Learning Of Recursion in the Best way

Share this Content

Recursion is a process of repeating items in a self-similar way. In programming, recursion is a method where a function calls itself repeatedly until a certain condition is met. When this happens, the function is said to have “self-recursed”.

It is a powerful tool, and it is not that difficult to understand. In this blog post, we’ll take a look at what the recursive approach is, how it works, and some of the things you can do with it.

Subscribe to Tech Break

How does Recursion work?

Recursion works by breaking a problem down into smaller and smaller pieces. For example, let’s say you wanted to find the factorial of a number. The factorial of a number is the product of all the positive integers less than or equal to that number. So, the factorial of 5 would be 5 * 4 * 3 * 2 * 1, or 120.

Explaining how recursion works by an example of factorial of five

To find the factorial of a number using recursion, you would first need to break the problem down into smaller pieces. So, you would need to find the factorial of 5, 4, 3, 2, and 1. Then, you would need to multiply those numbers together to get the final answer.

This is an example of how recursion works. You take a problem and break it down into smaller pieces until you get to a point where the problem can be solved. Then, you solve the smaller problems and work your way back up. So Recursive approach is a top-down approach.

Code:

#include <stdio.h> 
int rec(int);   //declaraing the recursive function 
int main() //main function 
{     
 int a, fact;
 printf("Enter any number: "); 
 scanf("%d",&a);
 fact = rec(a);
 printf("Fractional value=%dn", fact);
 return 0; 
}
int rec(int x) //recursive function definition 
{     
 int f;
  if (x == 1)
    return (1);
  else
    f = x * rec(x - 1);  //function is calling itself
  return (f);
} 

Input:

Enter any number: 5

Output:

Fractional value=120


Some common examples of recursion are:

  1. Finding the factorial of a number
  2. Calculating the Fibonacci sequence
  3. Generating a random number
  4. Sorting a list of numbers
  5. Tower of Hanoi
  6. Printing a list of numbers in reverse order

Why use recursion?

Recursion can be used to implement any data structure or algorithm.

For example, it can be used to implement linked lists, trees, and stacks. It can also be used to solve problems such as sorting and searching.

It has several advantages over other data structures and algorithms.

  1. Simplicity:
    Recursion can often be used to simplify a complex problem. By breaking the problem down into smaller pieces, the overall problem becomes much easier to solve. This is because each smaller problem is easier to solve than the original problem.
  2. Readability:
    Recursive code is often easier to read and understand than code that uses other methods to solve a problem. This is because the code is written in a step-by-step manner, making it easy to follow.
  3. Flexibility:
    It provides a great deal of flexibility when it comes to solving a problem. This is because there are many different ways to break a problem down into smaller pieces. This means that there are often multiple ways to solve a problem using recursion.
  4. Modularity:
    Recursive code is often more modular than code written using other methods. This means that it is easier to reuse code written using recursion. In addition, recursive code is often easier to debug and test.
  5. Efficiency:
    Recursive code is often more efficient than code written using other methods. This is because the code is written in a more concise manner, making it easier for the computer to process. In addition, recursive code is often easier to parallelize, making it more efficient to run on multicore processors.

When to use Recursion?

Recursion should be used only when it is the most appropriate data structure or algorithm for the problem. When deciding whether to use recursion, the following factors should be considered:

  1. The size of the data:
    If the data is small, recursion is usually the most appropriate data structure or algorithm. If the data is large, this approach can be very inefficient and should be avoided.
  2. The structure of the data:
    If the data is structured in a way that is conducive to recursion, the recursive approach is usually the most appropriate data structure or algorithm. If the data is not structured in a way that is conducive to recursion, it can be very inefficient and should be avoided.
  3. The complexity of the problem:
    If the problem is simple, the recursive approach is usually the most appropriate data structure or algorithm. If the problem is complex, this approach can be very inefficient and should be avoided.
  4. The type of solution:
    If the solution is elegant and easy to understand, the recursive approach is usually the most appropriate data structure or algorithm. If the solution is not elegant or easy to understand, this approach can be very inefficient and should be avoided.

Syntax:

So, from here we can understand that the syntax of the recursion function is

<returntype><recursive_function> (parameter_list) { statements; ... <recursive_function> (actual_argument); ... }

Let’s understand the recursive function’s part.

Read the following code part carefully

int rec(int x) //recursive function definition where "int x" is the parameter or argument like we did with every function 
{
  int f;
  if (x == 1)
    return (1);   
  //In these lines we are basically trying to say that if the input is 1 then   the output will be also 1 and if the input is any other   integer except 1 then the output will be like this-
  else
    f = x * rec(x - 1);  
  //Here function is calling itself. We can also write directly return (x * rec(x - 1));     
  return (f);
}

So, I hope you read this properly and understand how the whole thing works.

Types:

Now, there are two types of recursion.

  1. Direct recursion: When a function calls itself directly, then it is called a direct recursion. Example: Our previous example is actually a direct recursion.
  2. Indirect Recursion: When a function uses another function to recall itself then it is called an Indirect recursion.
    returntype func1(argument){ ... statements ... return func2(n);
    }
    returntype func2(argument)
    { ... return func1(n); }

So these are all about Recursion in the C language.


Facts:

  1. Any function, even the main() function can be recursive.
  2. Recursive programs are slower than non-recursive programs, cause it calls the function, so it needs to save their current state and then call them all again. So this is a disadvantage of the Recursive function.
  3. As recursive functions have intermediate states, so they required more memory than non-recursive functions. So this is also a disadvantage.
  4. A recursive function may or may not have a return statement.

If you know more facts about recursion, then you can tell us that in the comment section.

Share this Content
Snehasish Konger
Snehasish Konger

Snehasish Konger is the founder of Scientyfic World. Besides that, he is doing blogging for the past 4 years and has written 400+ blogs on several platforms. He is also a front-end developer and a sketch artist.

Articles: 214

Newsletter Updates

Join our email-newsletter to get more insights