Recursion: One more way.

So, now that you are familiar with iterators right? if not then

Iterators

Iterators are one of the fundamental concepts of programming. It is used to loop through all the elements of an array and perform the same operation on all of them or you can perform an operation number of times like printing a text 100 times with just a few lines of code with the help of iterators. In Python iterators are "for loop" and "while loop". Let's take an example of factorial using for loop.

def fact(n):
    f = 1
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        for i in range(1, n+1):
            f *= i
        return f

print(fact(5))
>>> 120

But there is one more way to do that and that is recursion.

Recursion

Recursion is a technique by which a function calls itself but in its simpler form. It is an important concept and most of the time it is used in data structures. Let's take the example of factorial using recursion:

def fact_re(n):
    if n == 1:
        return 1
    elif n == 0:
        return 1
    else:
        return n * fact_re(n -1)

print(fact_re(5))
>>> 120

So, here you can see that fact_re() is calling itself but the argument passed is less than that of the initial function. Hence, every time the function calls itself the argument becomes smaller and smaller, and at some point, it will become 1 since we have already provided a condition that if the argument is equal to 1 it will return 1 and the function will stop calling itself after reaching that condition.

Here, if you compare both functions, the iterator one and the recursion one, you will find that the recursion one contains fewer lines of code and that's what programmers want.

Programmers are so lazy.

Recursion helps to develop logical thinking and improves problem-solving skills.
It is easier to write and debug code for data structures using recursion.
It reduces time complexity for larger codes.

Types of recursion

Yes, recursion also has different types. It is of three types basically:

1. Linear recursion: If a recursive function is invoking itself at most one time during its execution then it is known as linear recursion. It can be a useful tool for processing a data sequence like lists or tuples in Python. For example:- The factorial function that we have seen above. Let's take another example to illustrate it better

def power(x, n):
    if n == 0:
        return 1
    else:
        return x * power(x, n - 1)


print(power(3, 4))
>>> 81

In the above example "x" is a number and "n" is the power. Here is the illustration:-

1. Binary Recursion: In binary recursion, a recursive function calls itself twice in each execution. Let's understand it by an example.

The most famous example is the Fibonacci series. It is a series of positive numbers in which each number is the sum of the preceding two numbers and it starts from 0 and 1.

         0 1 2 3 5 8 13 ....

This is what it looks like.
Now, let's print it using a recursive function.

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

print(fib(6))
>>> 8

This function returns the number at the given index, where n is the index that a user will provide. So here you can see line number 7, we have called the same function twice but in a much simpler form. Let's see another example where we will print an English ruler like

               ---- 0
               ---
               --
               -
               --
               ---
               ---- 1
               ---
               --
               -
               --
               ---
               ---- 2

this. Give it a try before we will dive into solving this using the recursive function.

Now if you have tried it by yourself let's solve it. Here, you can see a pattern i.e. dashes are decreasing from 4 to 1 and then increasing from 1 to 4, and at every line having maximum dashes, there is a number. So let's write a function that prints dashes.

def draw_line(tick_length, tick_label=""):
    line = tick_length * "-"
    if tick_label:
        line += ' ' + tick_label
    return line

print(draw_line(4, 0))
>>> ----

draw_line() function accepts two arguments the length of the line and if any line has a label prints it. Note: tick_label should be a string.
Now let's provide an interval so that the draw_line() function prints the line according to the length and interval.

def draw_interval(center_length):
    if center_length > 0:
        draw_interval(center_length - 1)
        draw_line(center_length)
        draw_interval(center_length - 1)

This function provides an interval to print the line.

In this function, you can see that the draw_interval() function calls itself twice but in its simpler form.

Now let's finally draw the ruler

def draw_ruler(line_length, ruler_length):
    draw_line(line_length, "0")
    for j in range(1, ruler_length + 1):
        draw_interval(line_length - 1)
        draw_line(line_length, str(j))

print(draw_ruler(5, 6))
>>>
----- 0
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 1
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 2
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 3
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 4
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 5
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 6

Congratulation, you have drawn your ruler using Python.

In the function draw_ruler() we have used for loop because this function cannot be broken into a smaller form to generate a continuous number.

1. Multiple Recursion:As the name suggests it is a process in which a function can call itself more than two times in each execution. This type of recursion is used to analyze the disk space usage of a file system because the number of recursive calls depends upon the entries within a given folder of a file system.

Summary

In this article, we saw another way of iteration using a function that calls itself in every execution but a simpler form and we are calling that function a recursive function.

Thanks For Reading