Recursive function

Definition of recursive function

Calling functions themselves in functions, we call such functions recursive functions.

Define recursive functions

# Factorization through recursive functions
def fun(n):
    if n == 1: # Recursive critical point (no longer calling the function itself)
        return 1
    else:
        return n * fun(n -1)

The advantage of recursive function is simple definition and clear logic Theoretically, all recursive functions can be written as loops, but the logic of loops is not as clear as recursion. Using recursive functions requires attention to prevent stack overflow In the computer, function calls are realized through the data structure of stack. Every time a function call is entered, the stack will add one layer of stack frame, and every time the function returns, the stack will reduce one layer of stack frame Because the stack size is not infinite, too many recursive calls will lead to stack overflow When trying to call fact(1000), the program will report an error.

To sum up, the advantage of using recursive functions is that the logic is simple and clear, but the disadvantage is that too deep calls will lead to stack overflow (i.e. occupy more memory space)

Pure function

Concept of pure function

In short, the return result of a function only depends on its parameters, and there are no side effects during execution. We call this function a pure function.

Three principles of pure function

1. Variables are only obtained within the scope of the function and passed in as parameters of the function
2. There will be no side effects, and the incoming data or other data (global variables) will not be changed
3. The same input guarantees the same output

Side effects of function

Side effects refer to that the function is called to complete the established calculation task of the function, but at the same time, a certain program changes the system environment because it accesses external data, especially because it writes the data.

Built in functions commonly used in python

• map function: the execution sequence will be mapped according to the provided function

  str() is a built-in function of python. This example is to change each element of list / tuple / string into str type, and then return it in the form of list.

   a = list(map(str,'python'))
  result:
  ['p', 'y', 't', 'h', 'o', 'n']
  

  Define a function and use the add method to add the two lists

  def add(x, y):
  
      return x+y
  
  
  list1 = [1, 2, 3]
  
  list2 = [4, 5, 6]
  
  a = list(map(add, list1, list2))
  
  print(a)
  

• filter function
  The filter() function is used to filter the sequence, filter out unqualified elements and return an iterator object. If you want to convert it to a list, you can use list() to convert it.

  The receives two parameters, the first is a function and the second is a sequence. Each element of the sequence is passed to the function as a parameter for judgment, and then returns True or False. Finally, the element that returns True is placed in the new list.

  Let's look at the source code of the filter function:

  def filter(function_or_none, sequence): # known special case of filter
      """
      filter(function or None, sequence) -> list, tuple, or string
      
      Return those items of sequence for which function(item) is true.  If
      function is None, return the items that are true.  If sequence is a tuple
      or string, return the same type, else return a list.
      """
      pass
  

  To use this function, we need to pass two parameters.

  1. function_or_none: judge the function. You can pass the function name or none
  2. sequence: iteratable object

  The above statement may be abstract. Let's take a look at an example

  #!/usr/bin/python3
   
  def is_odd(n):
  	# Judge to return odd number
      return n % 2 == 1
   
  # Filter with filter
  tmplist = filter(is_odd, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  newlist = list(tmplist)
  print(newlist)
  
  result:
  [1, 3, 5, 7, 9]
  
  

  • zip function

  The zip() function takes the iteratable object as a parameter, packages the corresponding elements in the object into tuples, and then returns a list composed of these tuples.

  If the number of elements of each iterator is inconsistent, the length of the returned list is the same as that of the shortest object. The tuple can be decompressed into a list by using the * operator.

  # Package as Yuanzu list
  test = zip([1, 2, 3], [2, 3, 4])
  
  return:
  [(1, 2), (2, 3), (3, 4)]
  

Anonymous function

Anonymous function values apply to simple function definitions.
Let's define a simple anonymous function

res = lambda a, b: a + b
print(res(1, 10))

result:
11

The code above is equivalent to our function below

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

However, python does not know that we use lambda functions in this way. The definition of anonymous functions is that functions are used immediately, that is, memory is released. Res above us is equivalent to defining a function, but the writing method res is always in memory and has not been released.

In python, anonymous functions are usually used in combination with filter and map, as shown in the following code:

li = [1, 2, 22, 30, 55]
res = filter(lambda x: x < 10, li)
print(res)

return:
[1, 2]

Anonymous functions can also be used in conjunction with expressions:

res = [(lambda x: x % 5 == 0)(i) for i in range(10)]

Three step operator

Suppose we need to judge the following code

if a>b:
    max = a;
else:
    max = b;

This can be done using a three-step expression

max = a if a>b else b

Like lambda function, three-step expression can make our code concise.

Partial function

Definition of partial function

In python, the built-in module functools provides many useful functions, one of which is the partial function. When the function parameters are too many and need to be simplified, use functools.partial to create a new function, which can fix some parameters of the original function, making it easier to call.

Partial function case

In the built-in function filter that we learned before, we need to pass in two parameters when calling, the first is function, and the second is the iterated type data that we need to filter.

We can pass in different filter conditions to get the data we need

li1 = [1, 20, 30, 100, 1001]
filter(lambda x: x > 3, li1)

In the above code, we just come over the data of one list, but what if there are multiple groups of list data to be filtered? What should we do?
Should we use the lambda function every time we filter a set of data like this?

li1 = [1, 20, 30, 100, 1001]
li2 = [1, 20, 30, 100, 1001]
li3 = [1, 20, 30, 100, 1001]
li4 = [1, 20, 30, 100, 1001]

filter(lambda x: x > 3, li1)
filter(lambda x: x > 3, li2)
filter(lambda x: x > 3, li3)
filter(lambda x: x > 3, li4)

We can use functools Partial can create a new function, create a new function through partial function, and pass in the parameters required by the original function in advance, making it easier for us to call.

from functools import partial

filter2 = partial(filter, lambda x:x>5)
print(list(filter2(li1)))