20. 재귀알고리즘(구구단, 별, 팩토리얼, 최대공약수)

■ 89. 재귀알고리즘 기본(구구단, 별)

 

★ 재귀함수란?

1. 재귀함수는 함수내에서 다시 자신을 호출한 후

   그 함수가 끝날 때 까지 함수호출 이후의 명령문이

   수행되지 않는다.

 

2. "반복문 + 스택구조가 결합된 함수"

 먼저 들어간 데이터가 가장 마지막에 나오는 구조

 나중에 들어간 데이터가 가장 먼저 나오는 구조(후입선출)

 

 

 

예제:

 

def hap(a,b):

    print (a+b)

   

def gop(a,b):

    print (a*b)

 

def hap_gop(a,b):

    hap(a,b)

    gop(a,b)

 

hap_gop(2,3)

 

결과: 5

           6

 

※설명:

hap_gop 함수는 그냥 a와 b 값을 받아와서

hap 함수와 gop 함수에 던져주는 역할만 수행한다.

hap_gop 함수가 hap 함수와 gop 함수를 호출했다

"그런데 재귀함수는 자기 자신의 함수를 호출한다"

 

예제:

 

def countdown(n):     # 3 , 2, 1

    if n==0:                     # n==0

        print('발사')     

    else:

        print(n)               # 3, 2, 1

        countdown(n-1)  # countdown(2), countdown(1), countdown(1)

       

countdown(3)       

 

 

 

※재귀함수를 사용했을때의 장점

 1. 코드가 간결해진다.

2. 루프문을 사용하지 않아도 된다.

 

 

문제274.

구구단 2단을 파이썬으로 구현하시오!

(loop문 사용)

 

for i in range(10,0,-1):

    print('2','x',i ,'=',i*2)

 

 

 

문제275.

위의 구구단을 재귀함수로 구현하시오

countdown(10)

-----------------------------------------

def countdown(n):   

    if n==0:                    

        print('끝')     

    else:

        print('2','x',i ,'=',n*2)              

        countdown(n-1) 

       

countdown(10

 ||

def countdown(n):   

    if n>0:

        print('2','x',i ,'=',n*2)              

        countdown(n-1) 

       

countdown(10) 

 

 

 

def countdown(num):

    if num>0:

        countdown(num-1)

        #함수내에서 다시 자신을 호출한 후

        #그 함수가 끝날 때 까지 함수 호출

        # 이후의 명령문은 실행하지 않는다.

        print('2x',num,'=',2*num)

   

countdown(10)

 

함수값이 되돌아가면서 대기타고 있다. 스택구조.

 

 

문제276.

loop 문을 이용하지 말고

재귀함수를 이용해서

아래의 결과를 출력하시오

 

 

def star_print(n):

    if n>0:

        star_print(n-1)

        print('★'*n)

  

print(star_print(7))

 

 

■ 90. 재귀알고리즘 기본(팩토리얼, 최대공약수)

 

 

문제277.

5! 를 파이썬으로 구현하시오

 

def fac(n):

    result=1

    for i in range(1,n+1):

        result=result*i

    return result

print(fac(5))

 

 

 

 

문제278.

fac 함수를 재귀함수로 구현하시오

 

def factorial(n):

    if n == 1:

        return 1

    return n * factorial(n - 1)

 

print(factorial(5))

 

 

 

 

문제279. (미리내는 내일의 점심시간문제)

loop 문을 이용해서 최대공약수를 구하시오!

---------------------------------------

print (find_gcd(20,16) )

4

 

print(find_gcd(108,72) )

36

 

기존 루프문

def find_gcd(a,b):

    x=min(a,b)

    while x>=1:      #

        if a%x==0 and b%x==0:

            result=x

            break       #while 문은 0<x<10  이렇게 범위 지정 아닌경우는

                       # 꼭 break 있어야 한다.

        else:

            x-=1

    return x

 

print(find_gcd(108,72))

----------------------------------------------------