Day 11. 재귀호출

 

1. 재귀호출(recursive call)

- 함수 안에서 동일한 함수를 호출하는 형태
- 여러 알고리즘, 고급 정렬 알고리즘 작성시 사용됨

 

• 재귀 호출(recursion)은 함수가 자기 자신을 다시 호출하는 기법을 말합니다. 재귀 호출을 사용하면 복잡한 문제를 간단하고 우아하게 풀 수 있지만, 잘못 사용하면 프로그램의 성능에 문제가 발생할 수 있습니다.
  
  
• 무한 재귀: 재귀 함수의 기본 케이스가 없거나 잘못되면 함수는 무한히 자신을 호출하게 됩니다. 이렇게 되면 프로그램은 결국 스택 오버플로우 에러를 발생시키게 됩니다.
  
  
• 성능: 재귀 호출은 간단하고 우아하게 보일 수 있지만, 반복문을 사용한 코드보다 더 많은 메모리와 시간을 소모할 수 있습니다. 특히 파이썬에서는 재귀 호출에 제한이 있으므로 (기본적으로 1000번) 큰 입력값에 대해 재귀 함수를 사용하면 문제가 발생할 수 있습니다.
  
  
• 메모리 사용: 모든 재귀 호출은 호출 스택에 저장됩니다. 따라서 많은 재귀 호출이 발생하면 메모리 사용량이 증가하게 됩니다.
  
  
• 가독성: 일부 사람들에게는 재귀 코드가 복잡하게 느껴질 수 있습니다.

 

• 재귀 호출 (예-1)

n ! = n  *  ( n - 1) !

1! = 1                  = 1 2! = 1 * 2                 =  2 * 1! 3! = 1 * 2 * 3           =  3 * 2! 4! = 1 *2 * 3 * 4     =   4 * 3 !

 

함수(n)은 n>1 이면 return n*함수(n-1) 함수(n)은 n=1 이면 return n (1! =1 자기 자신)

# 2! 함수(2)이면 2>1이므로 2*함수(1) 함수(1)이면 1이므로 return 2*1 결과는 2 # 3! 함수(3)이면 3>1 이므로 3*함수(2) 함수(2)는 위에 식에 의해 2! return 2*1 3*함수(2)는 3*2 = 3*2*1 결과는 6 # 4! 함수(4) 4>1 이므로 4*함수(3) 함수(3)은 위에 식에 의해 3!이므로 3*2*1=6 4*함수(3) = 4*6 = 4*3*2*1 결과는 24

 

def factorial(num):     if num > 1:       return num * factorial(num - 1)     else:       return num   for num in range(5):     print(factorial(num))

24 ----> 4*3*2*1

 

for num in range(5):     print(factorial(num))

0 1 2 6 24

 

 

• 재귀호출 (예-2 )
  회문(순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미)을 판별할 수 있는 함수를 만들어보자.
  * 단 회문이면  결과를 True, 아니면 False를 반환 

def palindrome(string):     if len(string) <= 1:       return True     if string[0] == string[-1]:       return palindrome(string[1:-1])    else:       return False   palindrome('짐사이이사짐')

True

• 재귀호출 (예-3 )
  - 정수 n을 입력받아 아래와 같이처리되는 프로그램을 만들어보자.
  
  * n이 홀수면3*n+1을 함(예: 3 입력 -> 10)
  * n이 짝수면 n을 2로 나눔 (10/2->5)
  * 이렇게 계속 진행하여 n이 결국 1이 될 때까지 위 조건을 반복하면서 실행

n 홀수 > 3 * n+1  n 짝수 > n / 2

# 3 : 10 # 10 : 5     3 * 5 + 1 : 16   8 : 8     4 : 4     2 : 2     1 : 1

 

(정답)

def func(n):     print(n)     if n==1 :       return '끝'     if n%2==1 :       return(func((3*n)+1))     else :       return(func(int(n/2)))   num = int(input('n을 입력하세요>>>'))   func(num)

n을 입력하세요>>>10 10 5 16 8 4 2 1 끝

 

(내코드)

def f(num):     if num == 1:       print(num)     elif (num%2) == 1:       return f(3 * num + 1)     else :       return f(num/2)   f(10)

1.0

 

 

•  [코드 분석 툴] (https://pythontutor.com/)

         Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ Ⅴ