[알고리듬] #85 재귀호출(recursive call)

 

파이썬 실습창을 열 수 있습니다.실습창 열기

 

재귀호출(recursive call)

재귀 호출적(recursive) 구조란 자기 자신(n차)을 정의하기 위해 자기 자신 보다 1차원 낮은 부분 집합(n-1차)을 사용하고 더욱이 그 부분 집합은 보다 낮은 차원의 부분 집합을 사용하여 정의하기를 반복하는 구조이다. 이와 같은 구조를 일반적으로 재귀 호출(자기 호출, recursion 또는 recursive call)이라 부른다.

 

자연수 n을 입력받아서,
재귀 호출 전략(recursive call strategy)으로 n부터 1까지 자연수를 출력하자.

 

1. 코딩하기

다음 코드를 실행하자.

def put(n):
    if n==0:return   # base case 탈출 조건(종료 조건)이다. 
    print(n,end=' ')
    put(n-1)         # inductive case 유도 조건(실행 조건)이다.
    return           # 함수의 끝에는 return이 있다. 보통은 생략한다.

# 최초 실행 부분(driver code, main code)    
n=int(input())
put(n)

재귀 호출(recursion mechanism, 자기 호출, 되부름)은 어떤 절차(함수 등)가 자신의 작업을 마치기 전에 자기 자신을 연이어 시작하도록 하는(recursive call) 문제 해결 전략(problem solving strategy)이다.
반복 구조(while, for)는 작업 처리가 선형으로서 앞으로만 진행되고, 처리 과정을 기억하지 않는다.
재귀 구조(recursion)는 처리 과정을 기억 시키면서 전진과 퇴각을 거듭하는 비선형 처리를 한다.
재귀 구조는 구문적인 기능(syntactical features)이 아닌 설계 전략(design strategy)이다.

 

이 그림은 recursive 전략의 개념도이다.
put(3)으로 호출한 경우의 예이다.

3 2 1로 출력되는 것을 이해하자.

• 함수를 호출하면 새로운 함수를 만들고 새로 만든 함수를 실행한다(현재의 함수는 동작 중지).
• .return에 의하여 자기를 호출한 함수로 되돌아 가서(back tracking) 중지된 동작부터 이어서 실행한다.  
  
  

알고리듬 전략 중에서 가장 중요하다.
이해가 될 때까지 분석하라.

 

2. 이해의 확인

다음 코드는 print문의 위치만 바뀌었다.

실행하기 전에 결과를 예측하여보라.

결과를 바르게 예측하면 이해를 한 것이다.

def put(n):
    if n==0:return 
    put(n-1) 
    print(n,end=' ')
    return 
n=int(input())
put(n)

   

자연수가 순서대로 출력되는 이유를 이해하라.

위의 개념도를 완전히 분석하라.

 

수고하셨습니다.

안녕!