這是我目前的代碼：
from loguru import logger
def fibonacci(n, s="% s"):
"""
Using recursive method
"""
# logger.debug(f"Finding {n}th Fibonacci number")
logger.debug(s % ("fib(%d)" % (n)))
a = 0
b = 1
if n <= 0:
return a
elif n in (1, 2):
return b
else:
return fibonacci(n - 1, s % ("fib(%d) %%s" % (n - 1))) fibonacci(n - 2, s % ("fib(%d) %%s" % (n - 2)))
我的目標是在日志中顯示遞回樹，例如fibonacci(5)：
fib(5)
fib(4) fib(3)
(fib(3) fib(2)) (fib(2) fib(1))
and so on...
這可能嗎？當前代碼沒有產生預期的輸出。
電流輸出：
fib(5)
fib(4) fib(4)
fib(4) fib(3) fib(3)
fib(4) fib(3) fib(2) fib(2)
fib(4) fib(3) fib(1) fib(1)
fib(4) fib(2) fib(2)
fib(3) fib(3)
fib(3) fib(2) fib(2)
fib(3) fib(1) fib(1)
想法：
uj5u.com熱心網友回復：
您可以定義一個類來保存二叉樹節點并構建樹作為遞回斐波那契函式的結果：
class BNode:
def __init__(self,value,left=None,right=None):
self.value = value
self.left = left
self.right = right
def print(self):
printBTree(self,nodeInfo=lambda n:(str(n.value),n.left,n.right))
from functools import lru_cache
@lru_cache() # optimize object count
def fiboTree(n): # (n is an index, not a count)
if n<2: return BNode(n)
a,b = fiboTree(n-2),fiboTree(n-1)
return BNode(a.value b.value,a,b)
輸出：
fiboTree(7).print()
13
____________/ \____________
5 8
_____/ \____ _______/ \______
2 3 3 5
/ \ __/ \_ __/ \_ _____/ \____
1 1 1 2 1 2 2 3
/ \ / \ / \ / \ / \ / \ __/ \_
0 1 0 1 1 1 0 1 1 1 1 1 1 2
/ \ / \ / \ / \ / \
0 1 0 1 0 1 0 1 1 1
/ \
0 1
你可以在這里找到這個printBTree功能
如果只需要說明呼叫層次，可以直接使用printBTree函式：
def fibo(n):
n=int(n) # linking with strings to let zero come out as a node
return (f"fibo({n})",[None,str(n-2)][n>1], [None,str(n-1)][n>1])
printBTree(5,fibo)
fibo(5)
____________/ \____________
fibo(3) fibo(4)
/ \ _____/ \____
fibo(1) fibo(2) fibo(2) fibo(3)
/ \ / \ / \
fibo(0) fibo(1) fibo(0) fibo(1) fibo(1) fibo(2)
/ \
fibo(0) fibo(1)
要隨時列印，我建議使用縮進來傳達呼叫層次結構，否則重復添加將很難與呼叫者相關聯。
def fibo(n,indent=""):
if n<2: return n
print(indent[:-3] "|_ "*bool(indent)
f"fibo({n}) = fibo({n-2}) fibo({n-1})")
return fibo(n-2,indent "| ") fibo(n-1,indent " ")
fibo(7)
fibo(7) = fibo(5) fibo(6)
|_ fibo(5) = fibo(3) fibo(4)
| |_ fibo(3) = fibo(1) fibo(2)
| | |_ fibo(2) = fibo(0) fibo(1)
| |_ fibo(4) = fibo(2) fibo(3)
| |_ fibo(2) = fibo(0) fibo(1)
| |_ fibo(3) = fibo(1) fibo(2)
| |_ fibo(2) = fibo(0) fibo(1)
|_ fibo(6) = fibo(4) fibo(5)
|_ fibo(4) = fibo(2) fibo(3)
| |_ fibo(2) = fibo(0) fibo(1)
| |_ fibo(3) = fibo(1) fibo(2)
| |_ fibo(2) = fibo(0) fibo(1)
|_ fibo(5) = fibo(3) fibo(4)
|_ fibo(3) = fibo(1) fibo(2)
| |_ fibo(2) = fibo(0) fibo(1)
|_ fibo(4) = fibo(2) fibo(3)
|_ fibo(2) = fibo(0) fibo(1)
|_ fibo(3) = fibo(1) fibo(2)
|_ fibo(2) = fibo(0) fibo(1)
這可以說明記憶的好處/效果：
def fibo(n,indent="",memo=None):
if n<2: return n
if memo is None: memo = dict()
print(indent[:-3] "|_ "*bool(indent) f"fibo({n})",end=" = ")
if n in memo:
print("taken from memo")
else:
print(f"fibo({n-2}) fibo({n-1})")
memo[n] = fibo(n-2,indent "| ",memo) fibo(n-1,indent " ",memo)
return memo[n]
fibo(7) = fibo(5) fibo(6)
|_ fibo(5) = fibo(3) fibo(4)
| |_ fibo(3) = fibo(1) fibo(2)
| | |_ fibo(2) = fibo(0) fibo(1)
| |_ fibo(4) = fibo(2) fibo(3)
| |_ fibo(2) = taken from memo
| |_ fibo(3) = taken from memo
|_ fibo(6) = fibo(4) fibo(5)
|_ fibo(4) = taken from memo
|_ fibo(5) = taken from memo
uj5u.com熱心網友回復：
一種方法可以是遞回中的每個呼叫將自身“報告”到它在樹的記錄中的位置。然后我們可以逐級迭代。就像是：
def f(n):
t = ["None"] * (2**(n-1) 1)
def g(n, i):
l = "(" if i & 1 else ""
r = ")" if not (i & 1) else ""
t[i] = "%sfib(%s)%s" % (l, n, r)
if n > 1:
g(n-1, 2*i 1)
g(n-2, 2*i 2)
g(n, 0)
print(t[0][0:-1])
i = 1
while 2**i-1 < len(t):
print(" ".join(t[2**i-1:2**(i 1)-1]))
i = 1
輸出：
f(5)
"""
fib(5)
(fib(4) fib(3))
(fib(3) fib(2)) (fib(2) fib(1))
(fib(2) fib(1)) (fib(1) fib(0)) (fib(1) fib(0)) None None
(fib(1) fib(0))
"""
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/334072.html