python #재귀함수

재귀함수

재귀함수는 자신을 호출하는 함수다. 반복동작을 짧게 구현할 수 있는 장점이 있지만 스택 사용량이 확 늘어나서 스택 오버플로우 문제 발생을 야기한다. 대부분 재귀는 루프로 대체 가능하기 때문에 루프로 대체하는 것이 좋다.

 

 

# 5! = 5*4*3*2*1

def fact1(num):
    if num == 1:     #끝나는 조건이 가장중요!
        return 1
    else:
        return num * fact1(num-1)

def fact2(num):
    res = 1
    for i in range(1,num+1):
        res *= i
    return res

def main():
    res = fact1(4)
    print('4!=', res)

    res = fact2(4)
    print('4!=', res)


main()

out)

 

 

Q. 피보나치수열 100항을 출력하라.

 

#재귀함수이용

def fibo1(num):
    if num <= 2:
        return 1
    else:
        return fibo1(num-1)+fibo1(num-2)
        
        
def main():
   
    for i in range(1, 101):
        print(fibo1(i))

#루프 이용해서
def fibo2(cnt):
    i, j, k = 1, 1, 0
    for x in range(1, cnt+1):
        if x<3:
            print(1, end='\t')
        else:
            k= i + j
            print(k, end='\t')
            i = j
            j = k
            
def main():

    fibo2(100)   

#리스트
def fibo3(cnt):
    res =[1,1]
    for i in range(2, cnt+1):
        res.append(res[i-1] + res[i-2])
    return res
    

def main():
    res = fibo3(100)    
    print(res)​

out)

모두 다 피보나치수열을 출력하지만 재귀함수는 출력하는 속도가 점차 느려진다.

그래서 재귀함수보다는 루프문으로 코드를 작성하는 것을 권장한다.