재귀 알고리즘 (1)

이번 단원은 정말 생각보다 많이 어려웠다. 어제 나름 집중도 잘하고 열심히 공부했다고 생각이 들었음에도 완벽히 이해하지 못해 오늘까지 시간이 필요했다.

 

재귀의 개념을 이해하더라도 코드를 어떻게 구현하는지, 실행과정이 어떻게 되는지를 알아야하기 때문에 상당한 시간이 필요했지만 앞서 먼저 공부한 친구의 도움을 빌려 어찌어찌 잘 해낸것 같다.

---

재귀 알고리즘

 

재귀란 어떠한 함수 또는 행동에서 자기 자신을 포함하고 다시 자기 자신을 사용하며 그로 인해 작업을 수행하는 것을 말한다. 하지만 자기 자신을 무한히 참조하기 때문에 무한 루프에 빠지지 않으려면 반드시 제어문이 필요하다.

 

일상생활 속에서 컴퓨터 화면이 자신의 화면을 출력한다면 그 출력물에서도 아래 사진과 같이 또 다른 자신의 화면을 호출할 것이다.

이것이 재귀의 개념이다.

 

팩토리얼

 

팩토리얼의 개념은 n 부터 1까지의 수를 모두 곱하는 것이다. n이 1이 아닐 때 항상 n * (n - 1) 을 하는 함수를 생성했을 때  (n - 1)을 n 으로 정의한다면 n부터 1까지 모두 곱하는 팩토리얼 함수가 생성될 것이다.

# 책에서 나온 코드

def fac(n):
    if n > 1:
        return n * fac(n - 1)
    else :	# n 이 0보다 작을 때 1을 반환
        return 1
        
# 내가 짠 코드

def fac(n):
	while n > 1:
    	return n * fac(n - 1)
    if n <= 1:
    	return 1

어느정도 재귀함수를 공부하고 나니 욕심이 조금 생겨 책을 보지 않고 나 스스로 재귀함수를 만들어보고 싶어졌다. 아래에 있는 코드는 내가 구현한 코드이다. 

 

이 짧은 코드를 구현하는데 많은 시행착오가 있었다. 처음에는 while 문을 이용해 n 이 1보다 크다면 계속 실행하게 만들었었는데 n 이 1보다 작을 때 return 값이 없어 오류가 발생했었다. 

 

해결 방법은 if 문을 따로 두어 모든 값에 return 값을 생성해서 해결했다. 

 

직접재귀

: 함수 스스로에서 자신을 호출하는 방법 

ex) 함수 a > 함수 a

 

간접재귀

: 자신을 참조하고 있는 다른 함수를 참조

ex) 함수 a > 함수 b > 함수 a

 

유클리드 호제법

 

두 정수값의 최대공약수를 구하는 재귀적 알고리즘 문제이다. 일반적으로 우리가 알고있는 최대공약수를 구하는 방법은 소인수분해를 한 뒤 그 수를 모두 곱하는 것이다.

 

하지만 유클리드 호제법에서는 MOD 연산을 통해 최대공약수를 구한다. 쉽게말해서 두 수를 나눈 뒤 나누었던 수와 나머지를 다시 나눈다. 

 

ex) 1202 / 2378 = 1...1176 > 1176 / 1202

 

나누어떨어질 때까지 이 과정을 반복하면 마지막 계산에서 나누는 수로 사용된 값이 두 수의 최대공약수이다. 이 때 같은 과정을 반복한다는 점에서 재귀 알고리즘을 이용할 수 있다는 것이다.

 

코드

def gcd(a: int,b: int):
    if b > a:
        a, b = b, a

    if a % b == 0:
        return b

    if b == 0:
        return a

    else:
        return gcd(b, a % b)

 

b가 나누는 수일떄 a와 b 의 나머지를 b의 자리에 놓는다면 나머지로 나눌 수 있을 것이다. 그리고 나누어지는 수(a)의 자리에 b를 넣어버리면 나누는 수와 나머지를 무한히 계산할 수 있다. 

 

재귀 알고리즘 분석

# 일반적인 재귀함수 - 1

def recur(n):
    if n > 0:
        recur(n - 1)
        print(n)
        recur(n - 2)

x = int(input('정수 입력 : '))
recur(x)

# 꼬리 재귀를 제거한 재귀함수 - 2

def recur(n):
    while n > 0:
        recur(n - 1)
        print(n)
        n = n - 2

x = int(input('정수 입력 : '))
recur (x)

# 스택으로 구현한 재귀함수 - 3

from stack import FixedStack

def recur (n):
    s = FixedStack(n)

    while (1):
        if n > 0:
            s.push(n)
            n = n - 1
            continue

        if not s. is_empty():
            n = s.pop()
            print(n)
            n = n - 2
            continue
        break

x = int(input('정수 입력 : '))
recur(x)

다음은 하나의 재귀 함수를 분석한 3가지 코드이다. 한줄한줄 읽으며 코드를 이해하고 결과값을 예상하면 재귀함수에 대해 조금이나마 잘 알 수 있을 것이다.