In programming, recursive processes are a concept that all programmers should have a deep understanding of, particularly when it comes to coding algorithms. In an effort to fully comprehend the power of a recursive programming approach, understanding the concept of recursion is a necessity. In this article, you’ll learn the definition of recursion and understand the concept with practical Python programming examples.

The Definition of Recursion

Recursion is a programming technique that allows the programmer to express operations in terms of themselves. Simply put, recursion means “defining something in terms of itself,” and it’s a fundamental concept of computer science. The most common application of recursion is in mathematical and computer science problems that require a function to repeat itself endlessly.

In terms of coding algorithms, recursion can be more efficient than iteration (using for or while technique) as it can reduce the amount of code necessary to iterate across a problem.

What is a Recursive Function?

A recursive function is a function that calls itself. At first glance, this may seem like an odd concept, however, recursive functions can be extremely powerful.

In order for a recursive function to work, it must meet two conditions:

  • The function must call itself.
  • It must have a base case.

A base case is a branch of a recursive function that doesn’t call itself, thereby halting the recursive loop. Without a base case, the loop will continue infinitely and crash the program.

Examples of Recursion in Python

Now we will look at a few practical examples using Python.

Factorials with Recursion

Let’s take a look at how recursive coding can be used to calculate the factorial of a number. A factorial is a number multiplied by all the numbers below it in sequence. For example, the factorial of 4 is:

4! = 4 * 3 * 2 * 1 = 24

A factorial value can be conveniently expressed using the exclamation mark (4!). Here is what the code for a recursive Python function for a factorial would look like:

  
def factorial_recursive(n):
    # Base case 
    if n == 0: 
      return 1

    # Recursive case 
    else: 
      return n * factorial_recursive(n-1)

The base case is defined as 0, which returns the value of 1. The recursive call is the return value multiplied by the function call with the number decremented by 1.

Fibonacci Numbers with Recursion

The Fibonacci sequence is a series of numbers in which the first two numbers are 0 and 1, and every other number is the sum of the previous two numbers.

0, 1, 1, 2, 3, 5, 8, 13, 21

The implementation of a recursive function for this sequence would look like this:

  
def Fibonacci_recursive(n):
    # Base case 
    if n == 1: 
        return 0
    elif n == 2:
        return 1
    # Recursive case 
    else: 
        return Fibonacci_recursive(n-1) + Fibonacci_recursive(n-2)

The code above has two base cases — one for n = 1, which returns 0 and one for n = 2, which returns 1. The recursive case then calculates the sum of the two previous numbers for any other value of n.

Conclusion

Recursion is a powerful tool for solving difficult problems, and can be a great addition to any programmer’s toolbox. Insights into recursion such as those discussed in this article will enable you to write more efficient algorithms and code.

References:
What is Recursion in Python — Tutorials Point
Recursion — GeeksforGeeks

Post Views: 328