[AG] 재귀함수

재귀함수

대부분의 인터넷 설명을 보다보면 재귀함수는 자기 자신을 호출하는 것이라고 표현한다.

하지만 실상은 반은 맞고 반은 틀린 말이다. 해당 표현으로 이해를 하게되면

결국 같은 함수로 오해하여 이해할수 있기 떄문이다.

 

재귀함수란 흔히 나 자신을 호출하는 함수라고 많이들 이야기 하지만 실제로는 코드가 재활용 되어 같은 이름의(다른함수)를 또 호출하는 것이다.

결론적으로 코드만 같고 다른 함수로 이해 하면 구조를 파악하기 쉽다.

장점

변수를 여럿 만들 필요가 없다.

예를들어 현재 상태를 저장해야 할 경우 tmp 변수를 만들기보다 상태를 메서드로 재귀적으로 호출하면서 변경된 상태를 전달 함으로써 변수의 수를 줄일 수 있다.

ex) While문이나 for문같은 반복문을 사용하지 않아도 되기에 코드가 간결해진다.

 

단점

지속적으로 함수를 호출하게 되면서 지역변수,  매개변수, 반환값을 모두 Stack에 저장해야한다.

그리고 이런 과정은 선언한 변수의 값만 사용하는 반복문에 비해서 메모리를 더 많이 사용하게되고,

이는 속도 저하로 이어진다.

ex) 함수 호출 -> 복귀를 위한 컨텍스트 스위칭에 비용이 발생하게됨

 

재귀를 배워야하는이유?

DFS, BFS, 그래프 등 필요한 알고리즘에 베이스가되기떄문.

 

연습문제1

 

번지점프

숫자 n을 입력받으세요.

숫자 n부터 0까지 Count down 했다가

다시 돌아오는 수를 출력 하세요.

ex) 입력 4

4 3 2 1 0 1 2 3 4

 

 

풀이 과정

 

Input으로 3을 입력하면 OutPut으로 3,2,1,0,1,2,3이 나와야하기떄문에

지역변수로 3을 입력받으면 재귀함수의 매개변수로 입력값을 던져주고

재귀를 호출하면서 입력값인 매개변수에 -1을 해주면 될것같다.

매개변수가 0이된다면 현재 매개변수를 출력해주고 return

재귀 호출전에 -1을 하면서 출력해주고(스택쌓이기전),

스택은 LIFO(후입선출) 이기 떄문에 0에서 return해주면 남아있는 데이터스택 3,2,1이

1 -> 2-> 3-> 순으로 return이 될것이다.

 

ex) 스택 데이터 삭제 순서

 

 

연습문제1 풀이

3을 입력받으면 재귀 호출 전 입력값으로 3,2,1이 출력되고

0이되면 return하면서 0이 출력되고

재귀호출 0뺴고 아직 return되지 않았으니 재귀호출 함수 밑에있는 출력을하고 return이 되는데

Stack메모리이기 떄문에 3,2,1순으로 들어온 데이터가 1,2,3으로 출력후 return이 된다.

 

출력결과

 

 

 

연습문제2

마이클잭슨 무브먼트

마이클 잭슨은 앞으로 갔다가 뒤로가는 문워크를 추곤합니다.

이 무브먼트를 재귀를 사용해 출력 해주세요

.

만약,

3 5 4 6 2 9 를 입력 받으면

3 5 4 6 2 9 2 6 4 5 3 이 출력 됩니다

 

 

풀이 과정

문제 1과 유사하지만 배열이나 string으로 받아야 할거같다.

인덱스로 출력을 하면 될것같다.

 

 

연습문제2 풀이

만약 123을 입력받으면 1 = 0번인덱스, 2 = 1번인덱스, 2 = 2번인덱스이기에

-1을 해줘서 마지막 인덱스일경우 return을 해준다.

나머지는 1번문제랑 똑같다.

 

출력결과

 

추가설명

만약 역순으로만 출력을 원한다면?

솔직히 저 문제들을 풀었으면 쉬울탠대 재귀호출전에 출력을 안하면 된다.

abc를 입력받았을경우 c에서 출력을하고 return이되고 b,a가 출력이 된다.