재귀호출(Recursive call)

함수 안에서 함수 자기자신을 호출하는 방식

보통 알고리즘에 따라서 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많음

 

파이썬 최대 재귀깊이 1000

 

재귀호출과 스택 넘침 현상

- 함수가 자기자신을 계속 호출하다가 최대 깊이(1000)를 초과하면 RecursiveError가 발생

 

재귀호출에 종료 조건 만들기

def hello(count):
	if count == 0:
    	return
        
       print('Hello, world!', count)
       
       count -=1
       hello(count)
       
hello(5)

 

 

피보나치 수열

- 재귀는 거꾸로 생각해야 한다(ex. fib(6)을 구하려면 fib(5) + fib(4)가 필요하다), 역산

   1 1 2 3 5 8 13 21 ...

f(n) = f(n-1) + f(n-2)

 

fib(6) = fib(5) + fib(4)

fib(5) = fib(4) + fib(3)

fib(4) = fib(3) + fib(2)

fib(3) = fib(2) + fib(1)

fib(2) = fib(1) + fib(0)

 

이렇게 반복되어서 나오기 때문에 시간이 오래걸림

#피보나치 수열
# fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3, ...

# 재귀
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# 반복문
def fib(num):
    result = []

    first = 1
    second = 1
    if (num > 1):
        result.append(first)
    result.append(second)
    for i in range(2, num):
        third = first+second
        result.append(third)
        first = second
        second = third

        print(first, second)

    return result.pop()

피보나치 수열은 다이나믹 프로그래밍을 이용해서 해결한다