재귀(recursion) 개념정리

재귀 함수

• 자기 자신을 호출하는 함수
• Base Case : 간단히 결과를 반환하는 부분
• Recursive Case : 자기 자신을 호출하는 부분

factorial - n==0 n! =1 // Base Case

                n>0   n! = n * (n-1)! // Recursive case

 

재귀를 활용한 flood fill 알고리즘

<코드>

#include <iostream>
using namespace std;
int n, Board[100][100];
void fill(int r,int c)
{
	if(r<0 || r>n-1 || c<0 || c> n-1) return; //경계면을 벗어나면 return 
	if(Board[r][c]) return; //벽이 있으면 return  
	Board[r][c] = 1;  
	fill(r-1,c);//위 
	fill(r+1,c);//아래 
	fill(r,c-1);//왼쪽 
	fill(r,c+1);//오른쪽 
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cin>>Board[i][j];
		}
	}
	int sr,sc;
	cin>>sr>>sc;
	fill(sr,sc);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			cout<<Board[i][j]<<' ';
		}
		cout<<'\n';
	}
	return 0;
}

<참고자료>

https://www.youtube.com/watch?v=Rs7Hz39hp5U&list=PL6YHvWRMtz7DS3hVaqMazHujPcKVfblQa&index=2