(Python)재귀함수

재귀함수

재귀함수는 정의 단계에서 자신을 재참조하는 함수를 뜻한다.

내부적으로 반복하다, 일정한조건을 만족하면 함수를 이탈하여 결과를 도출한다.

 

문제 풀이에서 DFS를 구현하는 가장 기본적인 방법으로 널리 사용되므로 잘 알아야 하고 쉽게 벽을 느낄수 있다.

 

재귀의특성

- 재귀는 같은 일을  하는 함수끼리 상태만 달리하여 호출한다.

- 무슨 일을 했는지는 중요하지 않다.

- 재귀호출이 무한히 발생할수 있다. (점화식)

 

 

def recursive():
    print("이것은 재귀함수입니다.")
recursive()


recursive() #함수 호출

이렇게 되면 무한히 출력된다.

 

def recursive(count):
	if count == 0:
    	return
    
    print("이것은 재귀함수입니다.")
    
    count -= 1
    recursive(count)

recursive(5) 실행

이렇게 코드를 쓰면 5번 출력하고 코드가 종료된다.

 

 

재귀 함수를 이용해 작성할 수 있는 몇가지 함수에 대해 알아보겠다.

 

1) 팩토리얼 함수

팩토리얼은 !를 기호로 사용하고 n부터 1까지 곱한 값을 구할때 사용한다

3! = 3*2*1

 

팩토리얼 함수는 반복분, 재귀함수 모두로 구할 수 있다.

 

반복문 사용 

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

 

# 재귀함수 사용 팩토리얼

def factorial(n):
    if n=1:						# n이 1 일때
        return 1				# 1 리턴후 재귀호출 끝
    return n * factorial(n-1)

 

2) 피보나치 수열

피보나치 수열 f(n) = f(n-2)+f(n-1) 라는 식을 가졌다

 

def fib(n):
    a,b = 1,1
    if n==1 or n==2:
        return 1

    for i in range(1,n):
        a,b = b, a+b

    return a

 

 이렇게 이해를 잘 했다고 하고

https://www.acmicpc.net/problem/17478 이 문제를 풀면 나처럼 왜 이런식으로 나오지? 라고 생각하는 사람이 있을 것 같다.

 

그 이유는 재귀함수의 흐름에 대해 잘 이해해야 한다.

재귀함수의 흐름이다.

 

즉 7번에는 "____라고 답변하였지1."   9번에 "라고 답변하였지1" 가 출력된다.

 

 

재귀함수의 장단점

 

장점 : 변수를 여러개 만들 필요가 없다. 메서드를 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일수 있다.

          코드가 간결해진다.

 

단점: - 지속적으로 함수를 호출하기때문에 변수,반환값을 process stack 에 저장해야한다 . 메모리 사용이 반복문에 비해 크고

이는 속도저하로 이어진다.

        - 복귀를 위한 컨텍스트 스위칭에 비용이 발생한다.

 

 

 

cf) stack 이란 후입선출인 자료구조이다

 

참고:https://catsbi.oopy.io/dbcc8c79-4600-4655-b2e2-b76eb7309e60

      https://seongonion.tistory.com/24