[재귀] Recursion - Python

재귀 사용하기

 

파이썬 기초 - Recursion

1. Factorial 구하기

- Factorial(5) = 1*2*3*4*5

- Factorial을 for문과 재귀로 구현

 

def factorial(n):
  res = 1
  for i in range(1,n+1):
    res = res*i
  return res

print(factorial(10))

# 재귀로 구현하기

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

print(factorial(3))
print(factorial(5))
print(factorial(10))

2. 최대공약수 구하기

- 두 수 a,b 중 작은 것으로 나누어 떨어지면 그 수가 최대공약수

- 나누어 떨어지지 않으면 작은 수를 1씩 감소시킨 값으로 a,b를 나눈다.

- a,b, 모두 나누어 떨어지면 최대공약수

def GCD(a, b):
  if a < b:
    small = a
    big = b
  else:
    small = b
    big = a
  
  if big % small == 0:
    return small
  else:
    div = small
    while div > 0:
      div = div -1
      if (big % div == 0) & (small % div == 0):
        return div

print(GCD(12,18))

 

3. 최대공약수 구하기 - 유클리드 방식

- 두 수 a,b, 중 더 작은 값이 b일 경우, function(b, a%b)를 재귀적으로 호출하며 최대공약수를 구한다.

- 재귀함수의 종료 조건은 function(b,0)일 경우 b를 return

def uclid(a,b):
  if b == 0:
    return a
  elif a > b:
    return uclid(b, a%b)
  elif a < b:
    return uclid(a, b%a)

print(uclid(12,18))

 

4. 재귀로 하노이의 탑 알고리즘

- A에 있는 원반을 B를 거쳐 C로 이동시킨다.

- 1. A에 있는 n-1개를 C를 이용해서 B로 이동

- 2. A에 있는 1개를 C로 이동

- 3. B에 있는 n-1개를 A를 이용해서 C로 이동

- 재귀 종료 조건은 원반의 개수가 1개일 때는 바로 목적지로 옮긴다.

def hanoi(a,b,c,n):
  if n==1:
    print(a,'->',c)
    return
  else:
    hanoi(a,c,b,n-1)
    hanoi(a,b,c,1)
    hanoi(b,a,c,n-1)

hanoi('A','B','C',3)