18. 파이썬 재귀함수

재귀 함수

 ▶ 정의 – Recursion(리커전, 되부름법)이란 ‘ 단위 프로그램에서 자신을 호출하여 문제를 해결하는 알고리즘 기법을 말한다. 즉 함수에서 자기 자신을 다시 호출하는 것을 말한다.’

이 기법은

          - 생각을 명료하게하고,

          - 표현을 단순하게 할 수 있지만,

          - 처리 시간이 길어지고, 자원 소모가 많은 특징이 있습니다.

  시간 지연과 자원 소모가 맣은 치명적 단점에도 불구하고 장점이 워낙 커서 가장 중요한 알고리즘 기법으로 인식되고 있다.

이러한 Recursion은 2개의 중요한 부분이 있고, 두 번째 부분에는 3개의 구성요소가 있습니다.

           - 종료 처리부 : 바로 처리할 수 있는 간단한 프로그램

           - 되부름 처리부

              ① 분할(divide) : 문제를 더 단순하거나 더 작게 하는 부분

              ② 호출(call) : 자신을 호출하는 부분

              ③ 결합(combine) : 부분의 해결을 전체로 결합하는 부분

 

[ 파이썬 재귀함수 팩토리얼 구하기 ]

  재귀(recursion)란 '자기 자신을 호출하는 것'을 의미합니다. 팩토리얼 연산은 다음과 같이 표현할 수있습니다.

n! = n * (n-1) * (n-2) * ....... * 1 f(4) = 4 * f(3)      = 4 * 3 * f(2)      = 4 * 3 * 2 * f(1)       = 4 * 3 * 2 * 1

파이썬 재귀함수 팩토리얼

[ 파이썬 재귀함수 피보나치 구하기 ]

파이썬 재귀함수 피보나치수열

[ 파이썬 재귀함수 유클리드호제법 ]

  최대공약수를 구하는 방법인 유클리드 호제법에 대해 알아봅시다

a = 280,  b = 30의 최대공약수  조건 ① a>=b  →  a = a % b         ② a < b → a와 b의 값을 바꿔줍니다.         ③ b==0이면 a가 최대공약수

 a=280, b=30일때 조건①  a=10, b=30이 됩니다.

                        조건② a와 b의 값을 바꿔줍니다 그러면 a=30, b=10이 됩니다.

                        조건① a=0 b=10이 되고 두 값을 바꿔주면 a=10, b=0이 됩니다.

                        b=0일때 a가 최대공약수가 됩니다.

※ a를 b로 나눈 나머지값을 b보다 a값이 항상 작습니다. 그러므로 조건2를 생각하지 않고 무조건 값을 바꿔주어도 됩니다.

파이썬 재귀함수 유클리드호제법