# Recursion
###### tags: `week7` `上課筆記`
### 1. factorial

def factorial(n):
    if n <= 1:return 1
    else:return n*factorial(n-1)

### 2. recursion深度：

import sys
sys.getrecursionlimit()
預設上限1000
改變上限：
sys.setrecursionlimit(10000)

### 3. power set:

def listofsub(s):
    n = len(s); l = list(s); o = []
    
    def subset(d,r):
        nonlocal n,l,o
        if d == n:
            o.append(r.copy())
            return
    
        subset(d+1,r);r.add(l[d])
        subset(d+1,r);r.remove(l[d])
    subset(0,set())
    return o    

### 4. merge sort

def merge(a,l,m,r):
    i,j,t= l,m+1,[]
    while i <= m or j <= r:
        if i > m:
            t.append(a[j]); j+= 1
        elif j>r:
            t.append(a[i]); i += 1
        elif a[i] < a[j]:
            t.append(a[i]); i+= 1
        else:
            t.append(a[j]); j += 1
    for k in range(1,r+1): a[k] = t[k-1]

def sort(a,l,r):
    if l >= r :
        return
    m = (l+r)//2
    sort(a,l,m)
    sort(a,m+1,r)
    merge(a,l,m,r)

def mergesort(a):
    sort(a,0,len(a)-1)
a = [4,5,6,3,8,7,9]
mergesort(a)

### 5.Goodstein sequence

def process(b,n):
    k,l =0,[]
    while b**(k+1)<=n:k+=1
    for i in range(k,-1,-1):
        q =n//(b**i)
        if q > 0:
            n -= q*(b**i)
            l.append([i,q])
    for x in l:
        if x [0]>=b:x[0] = process(b,x[0])
    return l
print(process(3,7625597485041))

def evaluate(b,l):
    v = 0
    for x in l:
        y = x[0]
        v += x[1]*b**(y if type(y) is int else evaluate(b,y))
    return v

def go(b,n):
    return evaluate(b+1,process(b,n))

### 6. Hanoi Tower

n = eval(input('n = '))
s = 0   #s代表狀態(stage)
p = [0]   #p[i]代表i號碟所在的柱子
for i in range(1,n+1):p.append(1)

def hanoi(m,x,y,z,/):
    '''從x號柱此刻最上方的m個碟子藉由中繼y柱搬到z柱'''
    global s
    if m == 1:
        for i in range(1,n+1):
            if p[i] == x:
                p[i] = z
                print('x:',x,'y:',y,'z:',z)
                print(f'第{(s:=s+1)}步:把{i}號碟從{x}號柱移到{z}號柱')
                break
    else:
        hanoi(m-1,x,z,y)
        hanoi(1,x,y,z)
        hanoi(m-1,y,x,z)

hanoi(n,1,2,3)

> [name=顧定克]
### 7. Hanoi四根柱子

def hanoi4(m,w=1,x=2,y=3,z=4):
    global steps
    if m==1:
        for i in range(1,n+1):
            if p[i]==w:
                p[i]=z
                steps+=1
                print(f'第{steps}步將{i}號環從{w}號柱移到{z}號柱')
                break
    elif m==2:
        hanoi4(1,w,y,z,x)
        hanoi4(1,w,x,y,z)
        hanoi4(1,x,w,y,z)
    else:
        hanoi4(m-2,w,y,z,x)
        hanoi4(1,w,x,z,y)
        hanoi4(1,w,x,y,z)
        hanoi4(1,y,w,x,z)
        hanoi4(m-2,x,w,y,z)

> [name=tzuenting]