How to implement pruning functions using high-order functions in python

This article mainly introduces in detail the relevant information on Python's use of higher-order functions to implement pruning functions. It has certain reference value. Interested friends can refer to it. I hope it can help everyone.

Case:

Sometimes, we want to add certain functions to multiple functions, such as timing statistics, logging, caching operation results, etc.

Requirements:

There is no need to add exactly the same code in each function

How to solve it?

Extract the same code and define it as a decorator

Find the Fibonacci sequence (golden section sequence), starting from the third item of the sequence, each item is Is equal to the sum of the first two terms

Find a staircase with a total of 10 steps. From the bottom to the top, you can only take 1 to 3 steps at a time, and you cannot go back. How many correct ways are there?

:

every time is 1 ~ 3 steps, the rest is 7-9 steps

If you take 1 step, you need to find the steps for the next 9 steps

            If you take 2 steps, you need to find the steps for the next 8 steps

                                                                                 steps, you need to find the steps for the next 7 steps

These 3 ways of walking are realized through recursion. The recursion is like a tree, and each recursion generates child node functions

and above When the two problems are solved through recursion, a problem will arise, a repeated solution problem, and the repeated solution process will be eliminated. This is called a pruning function in the C++ language

#!/usr/bin/python3
def jian_zhi(func):
  # 中间字典，判断已经是否求解过
  median = {}
  def wrap(*args):
    # 假如不在中间字典中，说明没有求解过，添加到字典中去，在的话，直接返回
    if args not in median:
      median[args] = func(*args)
    return median[args]
  return wrap
@jian_zhi
def fibonacci(n):
  if n <= 1:
    return 1
  return fibonacci(n-1) + fibonacci(n-2)
@jian_zhi
def climb(n, steps):
  count = 0
  # 当最后台阶为0的时候，说明最后只是走了一次
  if n == 0:
    count = 1
  # 当最后台阶不为0的时候，说明还需要走至少一次
  elif n > 0:
    # 对三种情况进行分别处理momo
    for step in steps:
      count += climb(n-step, steps)
       
  # 返回每次递归的计数
  return count
 
if __name__ == &#39;__main__&#39;:
  print(climb(10, (1, 2, 3)))
  print(fibonacci(20))

The so-called pruning function is just to ensure the uniqueness of each recursion function. It uses an intermediate dictionary to save the executed functions and parameters, and eliminates repeated function calls by judging the parameters.

The above is the detailed content of How to implement pruning functions using high-order functions in python. For more information, please follow other related articles on the PHP Chinese website!