16-2.Àç±Í È£Ãâ

16-2-°¡.ÀÚ½ÅÀ» È£ÃâÇÑ´Ù.

ÇÔ¼ö´Â ÀÏÁ¤ÇÑ ÀÛ¾÷À» ºÐ´ãÇϸç ÇÔ¼ö°¡ ¸ÃÀº ÀÛ¾÷À» ÇÒ ÇÊ¿ä°¡ ÀÖÀ» ¶§ ¿ÜºÎ¿¡¼­ ÀÌ ÇÔ¼ö¸¦ È£ÃâÇÏ´Â °ÍÀÌ º¸ÅëÀÌ´Ù. ¿¹¸¦ µé¾î ¹®ÀÚ¿­À» Ãâ·ÂÇÒ ÇÊ¿ä°¡ ÀÖÀ¸¸é printf¸¦ È£ÃâÇÏ°í Ä¿¼­¸¦ ¿Å±æ ¶§´Â gotoxy ÇÔ¼ö¸¦ È£ÃâÇϴµ¥ ÇÔ¼öµéÀº ÀÚ½ÅÀÇ ÀÓ¹«¸¦ ¸¶Ä£ ÈÄ ¿ø·¡ È£ÃâÇÑ °÷À¸·Î º¹±ÍÇÑ´Ù. ÀÌ°ÍÀÌ ÇÔ¼ö¸¦ »ç¿ëÇÏ´Â ÀϹÝÀûÀÎ ¹æ¹ýÀÌ´Ù. Àç±Í È£Ãâ(Recursive Call)Àº Ư¼öÇÏ°Ôµµ ÀڱⰡ ÀÚ½ÅÀ» È£ÃâÇÏ´Â Çü½ÄÀÌ´Ù.

ÀڱⰡ ÀÚ½ÅÀ» ´Ù½Ã È£ÃâÇÑ´Ù¸é »õ·Î È£ÃâµÈ ÀÚ½ÅÀÌ ¶Ç ´Ù¸¥ ÀÚ½ÅÀ» È£ÃâÇÏ°Ô µÉ °ÍÀ̹ǷΠ¾ð¶æ »ý°¢Çϱ⿡´Â ¹«ÇÑ ·çÇÁ°¡ µÉ °Íó·³ º¸ÀδÙ. ±×·¯³ª Àç±Í ÇÔ¼ö´Â ÀÏÁ¤ÇÑ Á¶°ÇÀÌ ¸¸Á·µÉ ¶§¸¸ ÀÚ½ÅÀ» È£ÃâÇϸç ÁßøµÈ È£ÃâÀ» Â÷·Ê´ë·Î ¹þ¾î³¯ ¼ö ÀÖ´Â ÀåÄ¡¸¦ °¡Áö°í Àֱ⠶§¹®¿¡ ½ÇÁ¦·Î ¹«ÇÑ ·çÇÁ´Â ¾Æ´Ï´Ù. ÀÏÁ¤ÇÑ È¸¼ö¸¸Å­¸¸ ÀÚ½ÅÀ» È£ÃâÇ쵂 ±× ȸ¼ö´Â Á¶°Ç¿¡ µû¶ó °¡º¯ÀûÀÌ´Ù.

Àç±Í È£ÃâÀº ¾ÆÁÖ Æ¯¼öÇÑ ¹®Á¦¸¦ Ç® ¶§ »ç¿ëµÇ´Âµ¥ ±¸Á¶°¡ Á¶±Ý »ý¼ÒÇÏÁö¸¸ ÀÏ´Ü Àͼ÷ÇØÁö¸é º¹ÀâÇÑ ¹®Á¦¸¦ ÇÔ¼ö Çϳª·Î °£´ÜÇÏ°Ô ÇØ°áÇÒ ¼ö ÀÖ´Ù. ¹®Á¦°¡ ³Ê¹« °Å´ëÇؼ­ ÇÑ ¹øÀÇ ÇÔ¼ö È£Ãâ·Î ÇØ°áÇϱâ Èûµé ¶§ Å« ¹®Á¦¸¦ ÀÛ°Ô ³ª´©¾î °¢ È£Ãâ½Ã¸¶´Ù Á¡ÁøÀûÀ¸·Î ¹®Á¦¸¦ ÇØ°áÇÏ´Â ¹æ¹ý(Divide and Conquer:ºÐÇÒ Á¡·É)À» ¾´´Ù. À̶§ ÀÛ°Ô ¸¸µç ¹®Á¦°¡ ¿ø·¡ ¹®Á¦¿Í °°Àº ±¸Á¶¸¦ °¡Áø´Ù¸é Àç±Í È£ÃâÀÌ ÇÊ¿äÇØÁø´Ù. ¶ÇÇÑ ´Ù·ç´Â ÀÚ·á ÀÚü°¡ Àç±ÍÀûÀÎ ±¸Á¶¸¦ °¡Áö°í ÀÖÀ» ¶§µµ Àç±Í È£ÃâÀ» »ç¿ëÇÑ´Ù.

Àç±Í È£ÃâÀ» »ç¿ëÇÏ´Â ÇÔ¼ö´Â ±¸Á¶°¡ µ¶Æ¯Çϱ⠶§¹®¿¡ ºÐ¼®Çϱ⠽±Áö ¾ÊÀ¸¹Ç·Î °³³äÀûÀ¸·Î ÀÌÇØÇϱ⠽¬¿î °£´ÜÇÑ ¿¹Á¦ºÎÅÍ ¸¸µé¾î º¸ÀÚ. Àç±Í È£ÃâÀÇ °¡Àå ÀüÇüÀûÀÎ ¿¹´Â ´©½Â ¿¬»êÀÌ´Ù. ´©½ÂÀº ÆÑÅ丮¾ó(!) ¿¬»êÀ̶ó°í Çϸç 1ºÎÅÍ ÁöÁ¤ÇÑ ¼ö±îÁö Á¤¼öµéÀÇ °öÀ¸·Î Á¤ÀǵȴÙ. ¼öÇÐÀûÀ¸·Î ÆÑÅ丮¾óÀ» Á¤ÀÇÇØ º¸¸é ´ÙÀ½°ú °°´Ù.

 

n! = 1*2*3*4*....*n

 

¿¹¸¦ µé¾î 3!=1*2*3=6ÀÌ µÇ°í 4!Àº 24°¡ µÈ´Ù. Á¤ÀÇ¿¡ ÀÇÇØ n!Àº n*(n-1)!°ú °°´Ù°í ÇÒ ¼ö ÀÖ´Ù. 1~n±îÁö °öÀº 1~(n-1)±îÁöÀÇ °ö°ú nÀ» °öÇÑ °Í°ú °°Àº °ÍÀÌ´Ù. ÀÌ °æ¿ì n!À» ±¸ÇÏ´Â ¿¬»êÀº nÀ» ±¸ÇÏ´Â »ó¼ö ¿¬»ê°ú (n-1)!À» ±¸ÇÏ´Â Á» ´õ °£´ÜÇÑ ¿¬»êÀ¸·Î ºÐÇÒµÉ ¼ö ÀÖ´Ù. À̶§ (n-1)! ¿¬»êÀº ¿ø·¡ ¿¬»êº¸´Ù ±Ô¸ð°¡ Á¶±Ý ÀÛ¾ÆÁö±â´Â ÇßÁö¸¸ ¿ø·¡ ¿¬»ê°ú ¸ð¾çÀÌ µ¿ÀÏÇÏ´Ù. À̶§ Àç±Í È£ÃâÀÌ ¹ß»ýÇÑ´Ù.

°°Àº ¹æ½ÄÀ¸·Î (n-1)!Àº (n-1)*(n-2)! ·Î ºÐÇÒµÉ ¼ö ÀÖÀ¸¸ç ÀÌ·± ½ÄÀ¸·Î ÆÑÅ丮¾ó ¿¬»êÀÇ ¹üÀ§¸¦ °è¼Ó ÁÙ¿© ³ª°£´Ù. ÀÌ °úÁ¤À» (n-1)ȸ ¹Ýº¹ÇÏ¸é °á±¹ ¿À¸¥ÂÊ Ç×Àº 1!ÀÌ µÇ¸ç 1!Àº ÀǽÉÇÒ ¿©Áö¾øÀÌ 1ÀÌ´Ù. ÀÌ ´Ü°è¿¡ À̸£¸é ´õ ÀÌ»ó Àç±Í È£ÃâÀÌ ÇÊ¿ä¾øÀ¸¸ç »ó¼ö°ªÀ» ¸®ÅÏÇÔÀ¸·Î½á Àç±Í È£ÃâÀ» ³¡³¾ ¼ö ÀÖ´Ù.

ÆÑÅ丮¾ó ¿¬»ê ÀÚü°¡ Àç±ÍÀûÀÎ ±¸Á¶¸¦ °¡Áö°í Àֱ⠶§¹®¿¡ Àç±Í È£Ãâ ÇÔ¼ö·Î ÀÌ ¹®Á¦¸¦ ½±°Ô ÇØ°áÇÒ ¼ö ÀÖ´Ù. ´ÙÀ½ ¿¹Á¦ÀÇ Factorial ÇÔ¼ö°¡ Àμö·Î Àü´ÞµÈ nÀ¸·ÎºÎÅÍ n!À» ±¸ÇÏ´Â ÇÔ¼öÀÌ´Ù.

 

¿¹ Á¦ : Factorial

#include <Turboc.h>

 

int Factorial(int n)

{

     if (n <= 1) {

          return 1;

     } else {

          return n*Factorial(n-1);

     }

}

 

void main()

{

     printf("1~5±îÁöÀÇ °ö=%d\n",Factorial(5));

}

 

main¿¡¼­ 5!À» ±¸ÇßÀ¸¹Ç·Î Ãâ·ÂµÇ´Â °á°ú´Â 120ÀÌ´Ù. ÀÌ ÇÁ·Î±×·¥ÀÌ ¾î¶»°Ô ½ÇÇàµÇ´ÂÁö ´Ü°èº°·Î ºÐ¼®ÇØ º¸ÀÚ. µð¹ö°Å·Î ´Ü°è ½ÇÇàÀ» ÇØ º¸¸é ¾Æ·¡ ¼ø¼­´ë·Î ½ÇÇàµÈ´Ù´Â °ÍÀ» Á÷Á¢ È®ÀÎÇÒ ¼ö ÀÖ´Ù.

 

 main¿¡¼­ 5!À» ±¸Çϱâ À§ÇØ Factorial(5)¸¦ È£ÃâÇÑ´Ù. mainÀº Factorial ÇÔ¼ö·Î Àμö¸¸ Àü´ÞÇÏ¸é ´©½ÂÀ» ±¸ÇÒ ¼ö ÀÖ´Ù°í ¾Ë°í ÀÖÀ¸¸ç 5!À» ±¸ÇÏ´Â ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇØ ÀÌ ÇÔ¼ö¸¦ È£ÃâÇß´Ù. ¿ÜºÎ¿¡¼­ ÇÔ¼ö¸¦ È£ÃâÇÑ °ÍÀÌ¸ç ¾ÆÁ÷ Àç±Í È£ÃâÀÌ ½ÃÀÛµÈ °ÍÀº ¾Æ´Ï´Ù.

 Factorial(5) ¼±µÎÀÇ Á¶°Ç¹®Àº Àμö°¡ 1ÀÌÇÏÀÎÁö º»´Ù. È£Ãâ¿ø¿¡¼­ 1!À» ¿äûÇß´Ù¸é ÀÌ °ªÀº »ó¼ö 1·Î Á¤ÀǵǾî ÀÖÀ¸¹Ç·Î 1¸¸ ¸®ÅÏÇÏ¸é µÈ´Ù. main¿¡¼­ Àü´ÞÇÑ Àμö nÀº 5ÀÌ¸ç ¾ÆÁ÷ 1ÀÌ ¾Æ´Ï¹Ç·Î ÀÌ Á¶°Ç¹®Àº °ÅÁþÀ̵Ǿî else ÀÌÇÏ°¡ ½ÇÇàµÈ´Ù. else¿¡¼­ 5!À» ±¸Çϱâ À§ÇØ ÀÌ ¹®Á¦¸¦ 5*(5-1)!·Î ºÐÇÒÇÑ´Ù.

n!ÀÇ Å« ¹®Á¦°¡ n*(n-1)!·Î ºÐÇҵǾúÀ¸¸ç ÀÌ ¹®Á¦¸¦ Ç®±âÀ§ÇØ Factorial(4)°¡ È£ÃâµÇ´Âµ¥ ÀÌ°ÍÀÌ ¹Ù·Î ÀÚ½ÅÀ» È£ÃâÇÏ´Â Àç±Í È£ÃâÀÌ´Ù. Factorial(5) ÇÔ¼ö´Â Factorial(4)¸¦ È£ÃâÇÏ°í ÀÌ ÇÔ¼ö°¡ ¸®ÅÏÇÒ ¶§±îÁö ´ë±âÇÑ´Ù.

 Factorial(5)¿¡ ÀÇÇØ È£ÃâµÈ Factorial(4)´Â °°Àº ¼ø¼­´ë·Î Factorial(3)À» È£ÃâÇÏ°í ÀÌ ÇÔ¼ö´Â ´Ù½Ã Factorial(2)¸¦ È£ÃâÇÏ¸ç °á±¹ Factorial(1)ÀÌ È£ÃâµÈ´Ù. Àç±Í È£ÃâÀÌ ¿¬¼âÀûÀ¸·Î ¹ß»ýÇϸ鼭 ¹®Á¦°¡ Á¡Á¡ ÀÛ¾ÆÁö°í ÀÖ´Â °ÍÀÌ´Ù.

 Factorial(1)Àº ÇÔ¼ö ¼±µÎ¿¡ ÀÖ´Â Á¶°Ç¹®¿¡ ÀÇÇØ 1À» ¸®ÅÏÇÑ´Ù. 1!Àº Á¤ÀÇ¿¡ ÀÇÇØ 1À̹ǷΠ´õ ÀÌ»ó Àç±Í È£ÃâÀ» ÇÒ ÇÊ¿ä¾øÀÌ »ó¼ö 1À» ¸®ÅÏÇϱ⸸ ÇÏ¸é µÈ´Ù. ÀÌ Á¶°Ç¹®Àº Àç±Í È£ÃâÀÌ Á¾·áµÇ´Â Á¾·á Á¶°ÇÀ̸ç Àç±Í ÇÔ¼ö°¡ ¸®ÅÏÇÏ´Â ¹ÝȯÁ¡À¸·Î ÀÛ¿ëÇÑ´Ù. ÀÌ Á¶°Ç¹®ÀÌ ¾øÀ¸¸é Àç±Í È£ÃâÀº ¹«ÇÑ È£ÃâÀÌ µÇ¾î ¹ö¸®Áö¸¸ Á¾·á Á¶°ÇÀÌ Àֱ⠶§¹®¿¡ ÀÚ½ÅÀ» È£ÃâÇÏ´õ¶óµµ ¾ðÁ¨°¡´Â ¿ø·¡ »óÅ·Πµ¹¾Æ°¥ ¼ö ÀÖ´Â °ÍÀÌ´Ù.

 Factorial(1) ÇÔ¼ö°¡ 1À» ¸®ÅÏÇϸé ÀÌ ÇÔ¼ö¸¦ È£ÃâÇÑ Factorial(2)´Â ¸®ÅÏµÈ 1°ú ÀÚ½ÅÀÇ Àμö 2¸¦ °öÇØ 2*1À» ¸®ÅÏÇÑ´Ù. ÀÌ ¸®ÅÏ°ªÀº Factorial(3)À¸·Î Àü´ÞµÇ¸ç ÀÌ ÇÔ¼ö´Â ´Ù½Ã 3*2¸¦ ¸®ÅÏÇÏ°í Factorial(4)´Â ÀÌ ¸®ÅÏ°ªÀ» ¹Þ¾Æ 4*3*2¸¦ ¸®ÅÏÇÑ´Ù. ÀÌ·± ½ÄÀ¸·Î ¿¬¼âÀûÀÎ ¸®ÅÏÀÌ ¹ß»ýÇÑ´Ù.

 ÃÖÃÊ È£ÃâµÈ ÇÔ¼ö Factorial(5)´Â ÀÚ½ÅÀ» È£ÃâÇÏ¿© ¾òÀº °á°úÀÎ 5*4*3*2*1À» °è»êÇÏ¿© ±× °á°ú¸¦ ¸®ÅÏÇÑ´Ù. ÀÌ ½ÃÁ¡¿¡¼­ Factorial ÇÔ¼ö´Â ½ÇÇàÀ» ¿ÏÀüÈ÷ Á¾·áÇÏ°í main ÇÔ¼ö·Î Á¦¾î¸¦ µ¹¸°´Ù.

 main ÇÔ¼ö´Â Factorial(5)°¡ ¸®ÅÏÇÑ °ª 120À» Ãâ·ÂÇÏ°í ÇÁ·Î±×·¥Àº Á¾·áµÈ´Ù. main ÇÔ¼ö´Â Factorial ÇÔ¼ö°¡ Àç±Í È£ÃâÀ» ÇÏ´ÂÁö ¾Æ´Ï¸é ´Ù¸¥ ¹æ¹ýÀ» ¾²´ÂÁö´Â ¸ð¸£Áö¸¸ ¾î·µç ÀÌ ÇÔ¼ö¸¦ È£ÃâÇÏ¸é ´©½ÂÀÌ °è»êµÈ´Ù´Â °ÍÀ» ¾Ë°í ÀÖÀ¸¸ç ¾à¼ÓµÈ ¹æ¹ýÀ¸·Î ÇÔ¼ö¸¦ È£ÃâÇÏ¿© °á°ú¸¦ ±¸ÇÑ °ÍÀÌ´Ù. ±×·¡¼­ ÇÔ¼ö´Â ÀÏÁ¾ÀÇ ºí·¢¹Ú½ºÀ̸ç ÀԷ¿¡ ´ëÇØ ¾à¼ÓÇÑ´ë·Î Ãâ·Â¸¸ ³ª¿À¸é µÈ´Ù.

 

ÀÌ ÇÁ·Î±×·¥ÀÇ ÀüüÀûÀÎ µ¿ÀÛÀ» ±×¸²À¸·Î ±×·Á º¸¸é ´ÙÀ½°ú °°´Ù. ÀÚ±â ÀÚ½ÅÀ» È£ÃâÇÒ ¶§¸¶´Ù Àμö°ªÀÌ 1¾¿ °¨¼ÒÇϸç ÃÖÁ¾ÀûÀ¸·Î ¹ÝȯÁ¡À» µ¹¾Æ ´Ù½Ã È£Ãâ¿øÀ¸·Î µ¹¾Æ°¡´Â ±¸Á¶¸¦ °¡Áö°í ÀÖ´Ù.

 

Factorial ÇÔ¼öÀÇ º»Ã¼¸¦ Á» ´õ °£´ÜÈ÷ ÀÛ¼ºÇϸé return (n <= 1 ? 1:n*Factorial(n-1)); ÇÑ Áٷεµ ¸¸µé ¼ö ÀÖ´Ù. µ¿ÀÏÇÑ ÄÚµåÀÌÁö¸¸ Á÷°üÀûÀÌÁö´Â ¸øÇϱ⠶§¹®¿¡ ÀÌ·± ½ÄÀ¸·Î Äڵ带 ¾ÐÃàÇÏ´Â °ÍÀº ÁÁÁö ¾Ê´Ù. if¹®À¸·Î Á¾·á Á¶°ÇÀ» ¸í½ÃÇÏ¿© ¹ÝȯÁ¡À» ¸íÈ®È÷ ÁöÁ¤ÇÏ´Â °ÍÀÌ Àб⿡ ÆíÇÏ°í Äڵ带 À¯ÁöÇϱ⿡µµ ÁÁ´Ù.

ÆÑÅ丮¾óÀ» ±¸ÇÏ´Â ÀÌ ¿¹Á¦´Â Àç±Í È£ÃâÀÇ °³³äÀ» Á÷°üÀûÀ¸·Î ÀÌÇؽÃÅ°±â À§ÇÑ ¿¹Á¦ÀÏ»ÓÀÌ´Ù. »ç½Ç ÆÑÅ丮¾ó ¿¬»êÀº ±»ÀÌ Àç±Í È£ÃâÀ» »ç¿ëÇÏÁö ¾Ê´õ¶óµµ ÈξÀ ´õ °£´ÜÇÑ ¹æ¹ýÀ¸·Î ¹®Á¦¸¦ ÇØ°áÇÒ ¼ö ÀÖ´Ù. ´ÙÀ½°ú °°ÀÌ Áö¿ªº¯¼ö m°ú for ·çÇÁ Çϳª¸¸ ¾²¸é Àç±Í È£Ãâ¾øÀ̵µ ¶È°°Àº ¿¬»êÀÌ °¡´ÉÇÏ´Ù.

 

int Factorial(int n)

{

     int i,m=1;

     for (i=1;i<=n;i++) {

          m*=i;

     }

     return m;

}

 

Àç±Í È£Ã⺸´Ù º¹ÀâÇÏÁöµµ ¾Ê°í ÇÔ¼ö È£Ãâ¿¡ ´ëÇÑ ¿À¹öÇìµå°¡ ¾ø¾î ¼Óµµ»óÀ¸·Îµµ ÈξÀ ´õ À¯¸®ÇϹǷΠÆÑÅ丮¾óÀ» ±¸Çϱâ À§ÇØ Àç±Í È£ÃâÀÌ ²À ÇÊ¿äÇÑ °ÍÀº ¾Æ´Ï´Ù. Àç±Í È£Ãâ ±¸Á¶¸¦ °¡Áö´Â ÇÔ¼ö´Â ÀÌ·± ½ÄÀ¸·Î ÀÏ¹Ý ÇÔ¼ö·Î º¯È¯ÇÒ ¼ö ÀÖÀ» °æ¿ì °¡±ÞÀûÀ̸é Àç±Í È£ÃâÀº ¾²Áö ¾Ê´Â °ÍÀÌ ´õ ÁÁ´Ù.

±×·¯³ª ¾î¶² °æ¿ì´Â Àç±Í È£ÃâÀÌ ¾Æ´Ï¸é µµÀúÈ÷ ¹®Á¦¸¦ ÇØ°áÇÒ ¼ö ¾ø´Â °æ¿ìµµ ÀÖ°í Àç±Í È£ÃâÀ» ¾µ ¶§ ±¸Á¶»óÀ¸·Î³ª ¼Óµµ»óÀ¸·Î ÈξÀ ´õ À¯¸®ÇÑ °æ¿ìµµ ÀÖ´Ù. Àç±Í È£ÃâÀº °³³äÀÌ Á¶±Ý »ý¼ÒÇÒ »ÓÀÌÁö ÀûÀç Àû¼Ò¿¡ »ç¿ëÇϸé Äڵ带 ÈξÀ ´õ °£´ÜÇÏ°í È¿À²ÀûÀ¸·Î ¸¸µé¾î ÁØ´Ù.