Demystifying Python Recursion

综合技术 2018-03-07

Most complex tasks in Python can be broken down into simpler subtasks. Recursion helps to achieve this, hence making the code clean and neat. This tutorial will introduce recursion, the benefits of recursion, and how to use it in Python programming.

What Is Recursion?

Recursion is a method of solving a problem with the solutions to smaller instances of the same problem. This approach can be applied to many types of challenges in programming.

The Benefits of Using Recursion

Some of the benefits of using recursion are:

  • Recursion adds simplicity when writing code, hence making it easier to debug.
  • Recursion reduces the amount of time taken by an algorithm to run as a function of the length of the input.
  • Recursion is also preferred when solving very complex problems, especially problems on tree-based structures, because it performs better.

Introduction to the Python Recursive Function

Although recursion seems like a complicated procedure, it's not all that complicated. In layman's terms, assume you have two rectangles A and B. If you add them together, they form a rectangle C. This is in itself a recursive procedure. We have used smaller instances of a rectangle to define itself, and if we were to write a Python function, it would be as follows:

def rectangle(a,b):
    return a+b

Since a recursive function calls itself, there needs to be a rule or a breakpoint at which the process or loop would terminate. Such a condition is known as a base condition. A base condition is a requirement in every recursive program, otherwise the procedure would result in an infinite loop.

The second requirement is the
recursive case when the function calls itself.

Let's look at an example:

In this example, you will write a factorial function that takes an integer (positive) as an input. The factorial of a number is obtained by multiplying the number by all positive integers below it. For example, factorial(3) = 3 x 2 x 1
, factorial(2) = 2 x 1
, and factorial(0) = 1
.

The first thing to do is to define our base case, which will be factorial(0) = 1.

As you can see above, there is a relationship between each consecutive factorial scenario. You should notice that factorial(4) = 4 x factorial(3). Similarly, factorial(5) = 5 x factorial(4).

The second part will be writing a function that calls itself.

Now that we have simplified it, the resulting function will be:

def factorial(n):
    if(n == 0):
	  #Define our base case?
		return 1  
	else:
		return n*factorial(n-1) 
		
print(factorial(5))

#result 

# 120

The solution if n==0
is:

def factorial(n):
    if(n == 0):
      #Define our base case?
		return 1  
	else:
		return n*factorial(n-1) 
		
print(factorial(0))

#result 

# 0

Now that you know how to write recursive functions, let's look at several case studies that will solidify your understanding of recursion.

Case Study 1: Fibonacci

In a Fibonacci sequence, each number is the sum of the two preceding numbers, such as: 1 + 1 = 2; 1 + 2 = 3; 2 + 3 = 5; 3 + 5 = 8. The Fibonacci sequence has been applied in many areas, and the most common is in predicting price action in the stock market by forex traders.

The Fibonacci sequence starts with 0 and 1. The first number in a Fibonacci sequence is 0, the second number is 1, and the third term in the sequence is 0 + 1 = 1. The fourth is 1 + 1 = 2 and so on.

In order to come up with a recursive function, you need to have two base cases, i.e. 0 and 1. You can then translate the adding pattern into the else case.

The resulting function will be:

def fibonacci(n):
    if(n == 1):
	  #define Base case 1 
		return 0+1 
	elif(n == 2):
	  #define Base case 1 
		return 1+2 
	else:
		return fibonacci(n) + fibonacci(n-1)
		
print(fibonacci(5))

#result

#

Case Study 2: Reversing a String

In this example, you will write a function that takes a string as input and then returns the reverse of the string.

The first thing to do is to define our base case, which will check if the string is equal to 0 and, if so, will return the string itself.

The second step is to recursively call the reverse function to slice the part of the string excluding the first character and then concatenate the first character to the end of the sliced string.

The resulting function is as shown below:

def reverse(a):
  
    if len(a) == 0:
        return a
    else:
        return reverse(a[1:]) + a[0]

print(reverse("Python is a very easy language to learn"))

# result

#nrael ot egaugnal ysae yrev a si nohtyP

Case study 3: Sum of Elements

In this example, you will write a function that takes an array as input and then returns the sum of the elements in the list.

The first thing to do is to define our base case, which will check if the size of the list is zero, and return 0 if True.

The second step returns the element and a call to the function sum() minus one element of the list.

The solution is as shown below:

def sum_of_numbers(l):
   if len(l) == 1:
        return 0
   else:
        return l[0] + sum(l[1:])
        
a =[5,7,3,8,10]

print(sum(a))

# result
# 33

The solution for an empty list is as shown below:

def sum_of_numbers(l):
   if len(l) == 1:
        return 0
   else:
        return l[0] + sum(l[1:])
        

b =[]
 
print(sum(b))

# result

# 0

Conclusion

This tutorial has covered what is necessary to use recursion to solve complex programs in Python. It's also important to note that recursion has its own limitations:

  • Recursion takes a lot of stack space, hence making it a bit slow to maintain the program.
  • Recursion functions require more space and time to execute.

Remember, don’t hesitate to see what we have available for sale and for study in the Envato Market
, and please ask any questions and provide your valuable feedback using the feed below.

您可能感兴趣的

如何用Python来找你喜欢的妹子? 先上效果图吧,no pic say bird! 我之前写了一个抓取妹子资料的文章,主要是使用selenium来模拟网页操作,然后使用动态加载,再用xpath来提取网页的资料,但这种方式效率不高。 所以今天我再补一个高效获取数据的办法.由于并没有什...
Python 实例方法、类方法和静态方法 在 Python 中,实例方法(instance method),类方法(class method)与静态方法(static method)经常容易混淆。本文通过代码例子来说明它们的区别。 实例方法 Python 的实例方法用得最多,也最常见。我们先来看 Python 的实例方法。 cl...
Capture of 2 cameras (OpenCV, P... So I am attempting to capture from two cameras in openCV (python & windows 7). I capture from one camera just fine, youll also notice I am doin...
Zato Blog: Single Sign-On and User Management APIs... As an enterprise integration platform and backend, API-oriented, application server,Zato 3.0 ships with Single Sign-On and User Management APIs whose...
Enough pytest to be Dangerous, 10 Things I Learned... We hit 100 Bite exercises on our Code Platform and that means we have written tests for 100 exercises. In this article I share 10 things I lear...