728x90
순환Recursion이란?
'순환'이란 자기 자신을 호출하는 함수를 뜻합니다. 아래처럼요.
void func(...){
...
func(...);
...
}
어떤 함수가 자기 자신을 다시 호출한다면, 당연히도, 한 번 그 함수가 실행되면 무한 루프에 빠지겠죠. 예를 들어 "Hello, World!"를 출력하는 함수를 작성하고 프린트문 뒤에 그 함수를 또 호출한다면, "Hello, World!"만 끝없이 출력될겁니다.
def prtHello():
print("Hello, World!")
prtHello()
if __name__ == "__main__":
prtHello()
// 출력
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
...
하지만 이러면 어떨까요?
def prtHello(n):
if(n==0):
return
else:
print("Hello, World!")
prtHello(n-1)
if __name__ == "__main__":
prtHello(5)
매개변수 값과 if문을 활용함으로써 recursion 함수임에도 무한 루프에 빠지지 않게했습니다. 위 코드를 실행하면 아래처럼 5번만 출력됩니다.
// 출력
Hello, World!
Hello, World!
Hello, World!
Hello, World!
Hello, World!
즉, 순환 함수라고 하더라도 적절한 조건만 맞춰주면 무한 루프에 빠지지 않슴다. 그 조건은 아래 두가지예요.
잘 보면 모든 경우를 조건화하여 반복하는 수학적 귀납법을 이용하는 걸 알 수 있습니다
def prtHello(n):
if(n==0): // 1. Base case
return // :순환에 빠지지 않는 적어도 하나의 경우가 있어야 한다.
else:
print("Hello, World!")
prtHello(n-1) // 2. Recursive case: 순환을 반복하다보면 Base case로 수렴해야 한다.
if __name__ == "__main__":
prtHello(5)
이 순환 함수를 이용하면 1부터 특정 숫자까지의 합을 구하거나 팩토리얼을 계산하거나, n번째 피보나치 수열의 항을 구하는 등의 순환 연산 도 쉽게 구할 수 있슴다
// 1부터 n까지의 합
def cnt(n):
if(n==0):
return 0
else:
return (n + cnt(n-1))
if __name__ == "__main__":
sum = cnt(5)
print(sum)
//출력
15
// 팩토리얼
def fac(n):
if(n==0):
return 1
else:
return (n * fac(n-1))
if __name__ == "__main__":
result = fac(5)
print(result)
//출력
120
// n번째 피보나치 수열의 항 구하기
def fib(n):
if(n<2):
return n
else:
return fib(n-1) + fib(n-2)
if __name__ == "__main__":
result = fib(7)
print(result)
//출력
13
더불어, 모든 순환함수는 반복문으로 변경 가능합니다. 그 역도 역시 성립합니다. 즉, 모든 반복문도 recursion으로 표현이 가능합니다. 하지만 순환함수는 복잡한 알고리즘을 단순하게 표현할 수 있는 대신 오버헤드가 있을 수 있다는 것도 기억해주세요.
학습 및 레퍼런스: inf.run/bbjY
728x90