글 읽기 - 재귀함수 호출, 끝나는 지점에 대한 질문입니다 !

woogie 2년 전 0

안녕하세요 재귀함수에 대해 이해가 필요한 학생입니다 !

재귀가 스택구조라 LIFO구조인것을 알겠고 수학적귀납법 형식인것은 알겠습니다만...

실제로 스택그림을 그려서 표현해보려고하니

함수의 호출부분과 끝나는 부분이 정확하게 이해가 되지않아

호출이 언제 빠져나오는지에 대한 개념이 잡혀있지 않습니다 ㅠ

혹시 n=3일때를 예시로

스택그림으로 그림 그려주실분 계신가요?

도움 주시면 정말 감사드리겠습니다.

#include <iostream>

using namespace std;

//재귀함수를 짤때 절차지향적이지 않고
//뭔가 도미노가 쓰러진다고 생각을 하고 짜야한다
//수학적 귀납법처럼 따라서 
//모든길을 끝까지 생각하지 말고
//몇항까지 갔을때 모든일이 일어난다고 과정을 해보자
//가장 중요한건 기저조건 = base condition 만들기

//핵심은 n번째 원판을 기둥 3으로 옮겨야한다.
//1~n-1 원판들이 모두 옮겨져야하고 더 나아가 2번으로 옮겨져야한다

void func(int a, int b, int n) {

  int cnt = 1;
  cout << "cnt: " << cnt << '\n';

  if(n==1){
    cout << a << ' ' << b << '\n';
    return;  
  } 
  //1. n-1개의 원판을 기둥 a에서 기둥 6-a-b로 옮긴다.
  func(a, 6-a-b, n-1);
  cout << "넘어왔을까?" << '\n'; 
  //2. n번 원판을 기동 a에서 기둥 b로 옮긴다.
  cout << a << ' ' << b << '\n';
  //3. n-1개의 원판을 기둥 6-a-b에서 기동 b로 옮긴다.
  func(6-a-b, b, n-1);
}

int main() {
  //가장 중요한건
  //1. 한번에 한개의 원판만 다른 탑으로 옮길 수 있다 
  //2. 쌓아 놓은 원판은 항상 위의것이 아래의것 보다 작아야 한다

  int n; //원판의 개수 
  cin >> n;

  func(1,3,n);

}

woogie 2년 전 0

함수 호출부분부터 끝나는 부분까지 천천히 써봤는데 답이 나왔습니다 !

무슨 함정에 빠진것 같이 답이 나오는 부분이 신기하네요...

근데 실제로 재귀를 사용하고 싶을때 언제 사용해야할지 감이 안옵니다 ㅠ

재귀함수를 이용해서 문제를 풀려고 할때

이건 재귀로 풀어야해 ! 혹은 이때 재귀함수를 호출해야지 !

라는 팁이랄까요?

그런게 있으실까요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

재귀함수 호출, 끝나는 지점에 대한 질문입니다 !

woogie 2년 전 0

woogie 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말