如何計算遞歸函數中值的重複次數？

Question

如果你有一個遞歸函數（例如斐波那契序列）：

def fib(n): 
    """Return Fibonacci of n; assumes n is an int >= 0.""" 
    if n == 0 or n == 1: 
     return 1 
    else: 
     return fib(n-1) + fib(n-2) 

如何將一個數，例如，當FIB（20）被調用時次FIB（2）的數量？

Answer 1

您可以使用字典來計算所有調用fib。字典必須在第一次撥打fib之前清除。

def fib(n): 
    global calls 
    """Assumes n an int >= 0 
    Returns Fibonacci of n""" 
    calls[n] += 1 
    if n == 0 or n == 1: 
    return 1 
    else: 
    return fib(n-1) + fib(n-2) 

Answer 2

如何：

def fib(n, counts_dict): 
    counts_dict[n] += 1 
    if n == 0 or n == 1: 
     return 1 
    else: 
     return fib(n-1, counts_dict) + fib(n-2, counts_dict 

凡counts_dict = collections.defaultdict(int)

Answer 3

def fib(n, x): 
    c = 1 if n == x else 0 

    if n == 0 or n == 1: 
     return 1, c 
    else: 
     fA, cA = fib(n - 1, x) 
     fB, cB = fib(n - 2, x) 
     return fA + fB, cA + cB + c 

如果

calls = defaultdict(int) 

在功能上，做其他事情之前更新在字典中的相應條目我有 沒有弄亂邏輯，這個函數接受n和x並返回一個元組(y, c) s.t.在計算過程中調用fib(n, _)=y和fib(x, _)時間爲c次。

這是一個更純粹的替代方案，涉及更新字典的其他解決方案。它基於OP僅需要對特定的k調用f(k, _)的次數的假設，並且因此避免填充僅需要一個值的字典。

Answer 4

您可以使用一個裝飾：

import functools 

def count(f): 
    """Count function calls.""" 
    @functools.wraps(f) 
    def counted(*args, **kwargs): 
     counted.count_calls += 1 
     return f(*args, **kwargs) 
    counted.count_calls = 0 
    return counted 

fib = count(fib) 
fib(5) 
fib.count_calls 
# 15 

或者，您現在可以使用這個裝飾和@符號前面加上任何函數定義：

@count 
def fib(n): 
    ... 

fib(5) 
fib.count_calls 
# 15 

注意，這個裝飾累積函數調用：

fib(5) 
fib(5) 
fib.count_calls 
# 30 

這是一個聰明的實現，它需要adv較少知道的抗體function attributes。請注意，最初的修飾器是從他的lecture on Memoization中討論的John DiNero的count功能修改而來，他在這裏解決了這個特定問題。

Answer 5

沒有全局變量：

from collections import defaultdict 
def fib(n, count=None): 
    if count is None: 
     count = defaultdict(int) 
    count[n] += 1 
    if n in (0, 1): 
     return 1, count 
    return fib(n - 1)[0] + fib(n - 2)[0], count 

的fib函數現在返回的元組：所述第一元件是所述期望值和所述第二元件是含有的fib功能多少次的每個值是所述信息的字典拜訪。

Answer 6

這就是我試過的...這樣想做工精細

def fib(n): 
    global counter 
    if (n == 0 or n == 1): 
     counter=counter+1 
     return 1 
    else: 
     counter=counter+1 
     return fib(n-1) + fib(n-2) 
def countfib(n): 
    global counter 
    counter = 0 
    fib(5); 
    global count 
    count=counter 
    counter = 0 
    return count 
counter=0 
count=0 
print fib(5) 
count=countfib(5) 
print count 

輸出：

Answer 7

如何使用的功能屬性。就像一個靜態變量。

def fib(n): 
    """Return Fibonacci of n; assumes n is an int >= 0.""" 
    If hasattr(fib, 'cnt'): 
     fib.cnt += 1 
    else: 
     fib.cnt = 1 
    if n == 0 or n == 1: 
     return 1 
    else: 
     return fib(n-1) + fib(n-2) 

fib.cnt =0 

Answer 8

這我不清楚到底是什麼，你要算重複值，所以我猜這是時代的（遞歸）函數被調用具有相同參數的數量（或一羣人，如果有多個）。

在下面的代碼中，名爲tally_recurring_args()的裝飾器用於在某些代碼中包裝該功能來執行此操作。爲了簡化事情並避免重新發明輪子，使用collections.Counter來計算函數的每個唯一參數組合的調用次數。這是該函數的一個屬性，因此每次調用裝飾函數時都可以在wrapper中輕鬆引用該屬性。

import collections 
import functools 

def tally_recurring_args(func): 
    func._args_counter = collections.Counter() @ add attribute to func 

    @functools.wraps(func) 
    def wrapper(*args): 
     key = ', '.join(str(arg) for arg in args) 
     func._args_counter[key] += 1 
     return func(*args) 

    return wrapper 

@tally_recurring_args 
def fib(n): 
    """Return Fibonacci of n; assumes n is an int >= 0.""" 
    if n == 0 or n == 1: 
     return 1 
    else: 
     return fib(n-1) + fib(n-2) 

print('fib(5) -> {}'.format(fib(5))) 
for args, count in sorted(fib._args_counter.items()): 
    print('fib({}): called {} time{}'.format(args, count, 
              's' if count > 1 else '')) 

輸出：

fib(5) -> 8 
fib(0): called 3 times 
fib(1): called 5 times 
fib(2): called 3 times 
fib(3): called 2 times 
fib(4): called 1 time 
fib(5): called 1 time