0

下面显示的代码有效。我认为使用递归在 Python 中无效。如何将其转换为 for 循环版本？

def fun(x1, y1, x2, y2, n, r=[]):
    if n<1 :
        return
    r.append( [[x1,y1],[x2,y2]])
    x3=(x1+x2)/2.0
    y3=(y1+y2)/2.0
    fun(x1,y1,x3,y3, n-1)
    fun(x3,y3,x2,y2,n-1)

    x4=(x2+y2-y3-x3)*0.7+x3;
    y4 = (y2 - x2 + x3 - y3)*0.7 + y3;
    fun(x3, y3, x4, y4, n - 1);

    x3 = (3* x1 + x2)/4;
    y3 = (3* y1 + y2)/4;
    x2 = (3*x2 + x1)/4;
    y2 = (3*y2 + y1)/4;
    x4 = (x2*1.7 - y2 + 2*x3 - x3*1.7 + y3)/2;
    y4 = (x2 + y2*1.7 - x3 + 2*y3 - 1.7*y3)/2;
    fun(x3, y3, x4, y4, n - 1);
    return r

print fun(200, 400, 200, 0, 9).__len__()
4

1 回答 1

2

您可能需要考虑使用memoize 之类的东西来通过使用更多内存来加速递归函数。本质上，它将任何调用的结果存储在缓存中。

添加以下代码

import collections
import functools

class memoized(object):
   '''Decorator. Caches a function's return value each time it is called.
   If called later with the same arguments, the cached value is returned
   (not reevaluated).
   '''
   def __init__(self, func):
      self.func = func
      self.cache = {}
   def __call__(self, *args):
      if not isinstance(args, collections.Hashable):
         # uncacheable. a list, for instance.
         # better to not cache than blow up.
         return self.func(*args)
      if args in self.cache:
         return self.cache[args]
      else:
         value = self.func(*args)
         self.cache[args] = value
         return value
   def __repr__(self):
      '''Return the function's docstring.'''
      return self.func.__doc__
   def __get__(self, obj, objtype):
      '''Support instance methods.'''
      return functools.partial(self.__call__, obj)

然后像这样装饰你的功能

@memoized
def fun(x1, y1, x2, y2, n, r=[]):
    ...

还要小心你的可选参数。由 所创建的列表r = []实际上将在所有带有 r 的 f 调用中共享。最好做这样的事情，这样每次都会创建一个新列表。

def fun(x1, y1, x2, y2, n, r=None):
    r = [] if r is None else r

一种更 Pythonic 的获取长度的方法是这样的

print len(fun(200, 400, 200, 0, 9))
于 2013-02-25T04:38:06.200 回答