재귀함수랑 친해지기 : 파스칼의 삼각형

파스칼의 삼각형
1
1     1
1     2     1
1     3     3     1
1     4     6     4     1
1     5     10    10    5     1
1     6     15    20    15    6     1
1     7     21    35    35    21    7     1
1     8     28    56    70    56    28    8     1
1     9     36    84    126   126   84    36    9     1
1     10    45    120   210   252   210   120   45    10    1
1     11    55    165   330   462   462   330   165   55    11    1

1. 먼저 첫번째 줄에는 숫자 1을 쓴다.
2. 그 다음 줄을 만들려면, 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다. 예를 들어, 네번째 줄의 숫자 1과 3을 더하여 다섯번째 줄의 4가 만들어진다.

-wikipedia

왼쪽 위,오른쪽 위에 있는 수를 더해서 만들어갑니다.
프로그램으로 만들기 위해 y(행),x(열)좌표로 나타내면

0,0
1,0     1,1
2,0     2,1     2,2
3,0     3,1     3,2     3,3
4,0     4,1     4,2     4,3     4,4
5,0     5,1     5,2     5,3     5,4     5,5

x==0일 때나 x==y일 때의 값이 1입니다.
왼 쪽 위,오른 쪽 위는 (y-1,x-1),(y-1,x)입니다.


그리하여 만들어진 소스


#include <stdio.h> get(int y,int x) { if(x==0 || y==x) return 1; return get(y-1,x-1) + get(y-1,x); } main() { int x,y; scanf("%d %d",&y,&x); printf("%d\n",get(y,x)); main(); }
재귀함수 아름답죠?