재귀함수 (팩토리얼, 피보나치)

*재귀 함수

함수가 자기 자신을 호출하는 함수. (반복문과 비슷하므로 무한루프에 빠지지 않기 위해서는 반드시 탈출 조건이 필요하다.)

 

*1부터 n까지의 합

 

def n_sum(n):
	if n==1:
    	return 1
    return n + n_sum(n-1)

1부터 n까지의 합을 , 반복문을 사용했을때와 재귀함수를 사용했을때의 차이점이 있다.

반복문 (for~range)을 사용한다면, 0부터 n을 향해가며 연산하기 때문에 bottom-up 방식

재귀함수의 경우는 n부터 시작하여 0을 향하여 연산하기 때문에 top-down방식이라고 한다.

 

 

* 팩토리얼

팩토리얼 : n!  = 1*2*3........*n

def factorial(n):
    if n == 1 :
        return 1
    print(n)
    return n * n_sum(n-1)

1부터 n까지의 합에서 +만 *로 바꾸어주면 팩토리얼을 구하는 재귀함수가 된다. 

 

 

 

 

 

* 피보나치 재귀함수

n번째 수 : n-1번째수 + n-2번째 수

def fibo(n):
    if n<2 : 
        return n
    return fibo(n-1)  +fibo(n-2)

 

 

*피보나치 반복문으로 구현

n = int(input())

arr = [0,1,1]
if n < 3 : answer = arr[n] 
else:
    while(True):
        arr.append(sum(arr[-2:]))

        if len(arr)>n : 
            answer = arr[n]
            break

print(answer)