• 모든 재귀 함수는 반복문(iteration)으로 변경 가능

• 그 역도 성립함. 즉, 모든 반복문 역시 재귀 함수로 변경 가능

• 재귀 함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 함

• 하지만 함수 호출에 따른 오버헤드가 있음(매개변수 전달, 스택에 액티베이션 생성) -> 속도 느려짐 (반복문이 재귀 함수보다 더 성능이 좋은 경우가 많다)

• 그럼 재귀를 왜 쓸까? n중 for문을 위해서. for문으로 설계하기엔 복잡하다

• 모든 프로그램은 호출 스택에 할당하는 공간이 정해져있기 떄문에 횟수에 제한 있다 -> stack over flow

• 무한루프에 빠지지 않기 위해선?

• • Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야한다

  • Recursive case : recursion을 반복하다 보면 base case로 수렴해야 한다

• 스택의 가장 상단에 현재 호출하고 있는 함수가 위치함. 그 아래에 있는 함수들은 각각의 매개변수를 저장하고 정지 상태로 있음(메모리 소비 많다)...오버 헤드 발생

• 스택에 데이터를 많이 쌓을수록 사용하는 메모리는 증가한다

1 ~ n까지 합

팩토리얼

x의 n승

피보나치

최대공약수 방법 1

최대공약수 방법 2

조합(combination)

문자열 출력

문자열 역순으로 출력

10진수를 2진수로 만들기

배열의 원소의 합 구하기

순차 탐색

최대값 구하기

2진 탐색