Iteration & Recursion

• Iteration과 Recursion의 속도: Recursion방식은 함수를 계속적으로 호출해야 하기 때문에, Iteration방식이 약간 더 빠르다.
• Recursion의 장점: Recursion방식은 Iteration방식으로 풀기 어려운 문제를 간단히(직관적) 풀 수 있다. (e.g. Hanoi Towers)

Iteration & Recursion 비교 코드

앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어나 어구(palindrome)을 생각해보자. 이 문제를 풀기 위해서는 문자열 $s$의 왼쪽과 오른쪽의 각 요소들을 대칭적으로 비교해야 한다.

• ? I did, did I?라는 예제로 두가지 방법을 비교해 보자.

s ='? I did , did I ?'

def iteration(s):
    for i in range(0,int(len(s)/2) ):
        if s[i] != s[-(i+1)]:
            return False
    return True

iteration(s)

s ='? I did , did I ?'

def recursive(s):
    if s == '':
        return True
    else:
        if s[0] ==s[-1]:
            return recursive(s[1:-1])
        else:
            return False

recursive(s)

• iteration
  • s[i] != s[-(i+1)]: ${(?,?),(I,I),…}$ 각 쌍들을 비교하는 역할을 한다.
  • 모두 같게 되면 True 반환한다.
• recursive
  • s[0] ==s[-1]: 현재 string의 맨앞과 맨뒤를 비교하는 역할을 한다.
  • recursive(s[1:-1]): 비교된 문자열을 제외한 string을 기존 함수를 재호출한다.
  • 모든 문자열이 제외되면, s == ''이 되며 True를 반환하게 된다.

More examples for recursion

• Factorial Function
  • 1부터 N까지의 곱을 누적해나가는 함수

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

• Fibonacci sequence(피보나치 수열)
  • 이전 두개의 값들의 합이 다음 값과 같은 수열

def fibonacci(n):
  if n <= 2:
      return 1
  else:
      return fibonacci(n - 2) + fibonacci(n - 1)

for i in range(1,11): # 1~10th의 피보나치 수열의 값
    print(fibonacci(i))

1
1
2
3
5
8
13
21
34
55

• Hanoi tower

• 3개의 원판(disks)가 있음
• 한번에 하나씩 옮길 수 있음
• 큰 원판이 작은 원판 위에 있을 수 없음
• 가장자리 왼쪽에서 가장자리 오른쪽으로 3개의 원판을 옮길 때 다음과 같은 순서대로 옮겨진다.

• 가장 큰 원판을 제외한 n-1개는 가운데 기둥으로 옮겨야 한다. hanoi(n - 1, start, end, middle)
• 가장 큰 원판을 마지막 기둥에 옮긴다. print(n, "번 원반을", start, "번 기둥에서" , end, "번 기둥으로 옮깁니다.")
• 가운데 옮겨진 n-1개의 원판 중 n-2개는 첫번째 기둥으로 옮겨야한다. hanoi(n - 1, middle, start, end)

def hanoi(n, start, middle, end):
  if n == 0:
      return 1

  hanoi(n - 1, start, end, middle)

  print(n, "번 원반을", start, "번 기둥에서" , end, "번 기둥으로 옮깁니다.")

  hanoi(n - 1, middle, start, end)

hanoi(3,1,2,3)

1 번 원반을 1 번 기둥에서 3 번 기둥으로 옮깁니다.
2 번 원반을 1 번 기둥에서 2 번 기둥으로 옮깁니다.
1 번 원반을 3 번 기둥에서 2 번 기둥으로 옮깁니다.
3 번 원반을 1 번 기둥에서 3 번 기둥으로 옮깁니다.
1 번 원반을 2 번 기둥에서 1 번 기둥으로 옮깁니다.
2 번 원반을 2 번 기둥에서 3 번 기둥으로 옮깁니다.
1 번 원반을 1 번 기둥에서 3 번 기둥으로 옮깁니다.