2023.04.12 파이썬의 재귀호출

1. 파이썬의  재귀호출(Recursive Call)

• 재귀 호출 분석
• 규칙
• 검증
• 재귀 호출의 전형적인 예 

---

29.재귀호출.ipynb

 

1. 파이썬의  재귀호출(Recursive Call)

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

 

 

1-1. 재귀 호출 분석

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

 

1-2. 규칙

• n! = n*(n-1)!

⭕규칙을 함수로 표현해 보기

✔ 자기 자신을 계속 호출 해주면서 곱하기를 해줘라.
  함수(n)은 n > 1 이면, return n * 함수(n-1) 
  함수(n)은 n = 1 이면, return n 

1-3. 검증

1.  2! (2팩토리얼)
   함수(2)이면 2 > 1 이므로, 2 * 함수(1)
   함수(1)이면 1 이므로, return 2 * 1
   결과는 2
   
   
2.  3! (3팩토리얼)
   함수(3)이면 3 > 1 이므로, 3 * 함수(2)
   함수(2)는 1번식에 의해 2!이므로, return 2 * 1
   3*함수(2)는 3 * 2 = 3 * 2 * 1
   결과는 6
3.  4! (4팩토리얼)
   함수(4)이면 4 > 1 이므로, 4 * 함수(3)
   함수(3)는 2번식에 의해 3*2*1 = 6
   4 * 함수(3) = 4*6 = 4*3*2*1
   결과는 24
   
   

def factiorial(num):
  if num > 1:
    return num * factiorial(num-1)
  else:
    return num
    
    
    
factiorial(4) # 4!(4팩토리얼)테스트

1-4. 재귀 호출의 전형적인 예 

• 재귀 함수는 내부적으로 스택처럼 관리된다.
• 파이썬에서만 나타는 규칙 - 재귀함수의 깊이가(한번에 호출되는) 1000회 이하로 되어야 한다.

 

⭕코드분석 사이트 

https://pythontutor.com/visualize.html#code=%23%20factorial%20%ED%95%A8%EC%88%98%20%EC%95%88%E[%E2%80%A6]live.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false

 

 

문제(기러기,인도인,스위스....)

회문(순서를 거꾸로 읽어도 제대로 읽은것과 같은 단어와 문장을 의미)을 판별할 수 있는 함수를 리스트 슬라이싱과 재귀 함수를 활용하여 만들어보자. 
(단, 회문이면 결과를 True,아니면 False를 반환)

def palindrome(str):
  if len(str) <= 1:
    return True
  if str[0] == str[-1]:
    return palindrome(str[1:-1])
  else:
    return False

palindrome('안녕하세요')