import sys
from functools import wraps
def trace(func):
func_name = func.__name__
separator = '| '
trace.recursion_depth = 0
@wraps(func)
def traced_func(*args, **kwargs):
print(f'{separator * trace.recursion_depth}|-- {func_name}({", ".join(map(str, args))})')
trace.recursion_depth += 1
result = func(*args, **kwargs)
trace.recursion_depth -= 1
print(f'{separator * (trace.recursion_depth + 1)}|-- return {result}')
return result
return traced_func
def factorial_iterative_while(n):
result = 1
while n>= 1:
result *= n
n-= 1
return result
def factorial_recursive(n):
if n <= 1:
return 1
else:
return n * factorial_recursive(n-1)
print(factorial_iterative_while(5))
factorial_recursive = trace(factorial_recursive)
print(factorial_recursive(5))
def fibonacci_iterative(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
def fibonacci_recursive(n):
if n < 2:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive( n - 2 )
print(fibonacci_iterative(6))
fibonacci_recursive = trace(fibonacci_recursive)
print(fibonacci_recursive(6))
def list_sum_iterative(l):
result = 0
for v in l:
result += v
return result
def list_sum_recursive(l):
if len(l) == 0:
return 0
return l[0] + list_sum_recursive(l[1:])
print(list_sum_iterative([2,4,5,6]))
list_sum_recursive = trace(list_sum_recursive)
print(list_sum_recursive([2,4,5,6]))
def GCD_recursive(a, b):
if b == 0:
return a
else:
return GCD_recursive(b, a % b)
GCD_recursive = trace(GCD_recursive)
print(GCD_recursive(32, 12))
def multiply_recursive(n, a):
if n == 1:
return a
return multiply_recursive(n-1, a) + a
multiply_recursive = trace(multiply_recursive)
print(multiply_recursive(5, 4))
def exp_iterative(a, n):
base = a
for i in range(n-1):
a *= base
return a
def exp_recursive(a, n):
if n == 1:
return a
return exp_recursive(a, n-1) * a
exp_recursive = trace(exp_recursive)
print(exp_recursive(3, 3))
def iterative_str_len(s):
result = 0
for i in range(len(s)):
result += 1
return result
def recursive_str_len(s):
if s == "":
return 0
return recursive_str_len(s[1:]) + 1
recursive_str_len = trace(recursive_str_len)
print(recursive_str_len('hola'))
def quicksort(a):
if len(a) <= 1:
return a
pivot = a[len(a) // 2]
left = [x for x in a if x < pivot]
middle = [x for x in a if x == pivot]
right = [x for x in a if x > pivot]
return quicksort(left) + middle + quicksort(right)
quicksort = trace(quicksort)
print(quicksort([2,1,6,5]))
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
def traverse(head):
if head is None:
return
print(head.data)
traverse(head.next)
item1 = Node('dog')
item2 = Node('cat')
item3 = Node('rat')
item1.next= item2
item2.next = item3
traverse(item1)
head = Node("dog", Node('cat', Node('rat', None)))
traverse(head)
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def preorder(root, path =''):
if root:
path += str(root.data) + '-'
path = preorder(root.left, path)
path = preorder(root.right, path)
return path
def inorder(root, path =''):
if root:
path = inorder(root.left, path)
path += str(root.data) + '-'
path = inorder(root.right, path)
return path
def postorder(root, path =''):
if root:
path = postorder(root.left, path)
path = postorder(root.right, path)
path += str(root.data) + '-'
return path
if __name__ == '__main__':
root = Node('F')
root.left = Node('D')
root.left.left = Node('B')
root.left.left.right = Node('C')
root.left.right = Node('E')
root.right = Node('I')
root.right.left = Node('G')
root.right.left.right = Node('H')
root.right.right = Node('J')
print("Preorder", preorder(root))
print("Inorder",inorder(root))
print("Postorder", postorder(root))
def towers_hanoi(n, source, destination, aux):
if n == 1:
print("Move disk 1 from source", source, 'to destination', destination)
return
towers_hanoi(n-1, source, aux, destination)
print("Move disk", n, "from source", source, 'to destination', destination)
towers_hanoi(n-1, aux, destination, source)
n = 3
towers_hanoi(n, 'A', 'C', 'B')