Note 001 Recursive

#include
int fibonacci(int n);
int factorial(int n);

int main()
{
int num, result;
while(1){
printf("0ÀÌ»ó ¼ýÀÚ¸¦ ÀÔ·ÂÇϼ¼¿ä. (0:Á¾·á): ");
scanf("%d", &num);
// ÇǺ¸³ªÄ¡ ÇÔ¼ö È£Ãâ
result = fibonacci(num);
printf("Fibonacci(%d) = %d\n", num, result);
// ÆÑÅ丮¾ó ÇÔ¼ö È£Ãâ
result = factorial(num);
printf("Factorial(%d) = %d\n\n", num, result);
// numÀÌ 0À̸é Á¾·áÇÑ´Ù.
if(num==0)
break;
}
return 0;
}

// ÇǺ¸³ªÄ¡ ÇÔ¼ö
int fibonacci(int n)
{
int result;
// Á¤ÀÇ¿¡ ÀÇÇÏ¿© nÀÌ 0À̸é 0À», 1À̸é 1À» ¹ÝȯÇÑ´Ù.
if(n==0)
result=0;
else if(n==1)
result=1;
// nÀÌ 1º¸´Ù Å« °æ¿ì¿¡´Â
// ¹Ù·Î ¾ÕÀÇ µÎ ¼ö¸¦ ´õÇÑ °ªÀ» ¹ÝȯÇÑ´Ù.
// ¹Ù·Î ¾ÕÀÇ µÎ ¼ö ¶ÇÇÑ ÇǺ¸³ªÄ¡ ¼ö¿­ÀÇ ¼ö À̹ǷÎ
// Àç±Í·Î È£ÃâÇÑ´Ù.
else
result=(fibonacci(n-2)+fibonacci(n-1));
return result;
}

// ÆÑÅ丮¾ó ÇÔ¼ö
int factorial(int n)
{
int result;
// Á¤ÀÇ¿¡ ÀÇÇÏ¿© nÀÌ 0 ¶Ç´Â 1À̸é 1À» ¹ÝȯÇÑ´Ù.
if(n==0 || n==1)
result=1;
// nÀÌ 1º¸´Ù Å« °æ¿ì¿¡´Â
// ¹Ù·Î ¾ÕÀÇ ¼ö¿Í nÀ» °öÇÏ¿© ¹ÝȯÇÑ´Ù.
// ¹Ù·Î ¾ÕÀÇ ¼ö ¶ÇÇÑ ÆÑÅ丮¾óÀÇ °á°ú À̹ǷÎ
// Àç±Í·Î È£ÃâÇÑ´Ù.
else
result=n * factorial(n-1);
return result;
}



http://kr.blog.gugi.yahoo.com/duduzoa/folder/9.html



int factorial(int n)
{
if(n <= 1) return 1; // 1 ÀÎ °æ¿ì 1À» ¸®ÅÏÇÏ¿© ´äÀ¸·Î ÁØ´Ù.
else return ( n*factorial(n-1)); // 1 ÀÌ»óÀÎ °æ¿ì ¼ýÀÚ¸¦ Çϳª ³·Ã߾ ´Ù½Ã factorialÇÔ¼ö¸¦ ºÎ¸¥´Ù.
}
void main()
{
int n;
scanf("%d", &n); // ¿øÇÏ´Â ¼ýÀÚ¸¦ ¹Þ¾Æ n¿¡ ÀúÀåÇÑ´Ù.
printf("%dÀÇ ÆÑÅ丮¾ó°ªÀº" , factorial(n)); // factorialÇÔ¼ö¸¦ ºÎ¸¥´Ù.
}
Ãßõ(0) ½ºÅ©·¦ (0) Àμâ






http://ask.nate.com/knote/view.html?num=19874


³×ÀÌÆ® Áö½Ä¿¡¼­ ³ª¿Â. C/C++



¾Æ·¡ÀÇ ÇÁ·Î±×·¥Àº °ø°£º¹Àâµµ(SC: Space Complexity) ¸é¿¡¼­
Àç±Í(Recursive) ¾Ë°í¸®Áòº¸´Ù ¿ì¼öÇÑ ¹Ýº¹(Iterative)¾Ë°í¸®ÁòÀ»
»ç¿ëÇÏ¿© ÆÑÅ丮¾ó °è»êÀ» ±¸ÇöÇÑ ¼Ò½ºÀÔ´Ï´Ù.

13! ÀÌ»óÀÇ °ªÀº 4¹ÙÀÌÆ® Á¤¼ö ÀÚ·áÇü(int)¿¡ ÀúÀåÀÌ ºÒ°¡´ÉÇÒ Á¤µµ·Î
Å«¼ö°¡ µÇ´Âµ¥, À̶§¿¡´Â 0¿µÀ¸·Î È­¸é Ç¥½ÃÇϵµ·Ï ¹æ¾î ÇÁ·Î±×·¡¹ÖÀÌ
±¸ÇöµÇ¾î ÀÖ½À´Ï´Ù.


//----------------------------------//
// *** ÆÑÅ丮¾ó °è»ê ÇÁ·Î±×·¥ *** //
// "Factorial.cpp" //
// ... Using Visual C++ 6.0 ... //
// ------------------------------ //
// ÆÑÅ丮¾ó °è»êÀ» ¹Ýº¹ °è»ê //
// ¾Ë°í¸®ÁòÀ¸·Î ±¸ÇöÇÑ Pgm ÀÔ´Ï´Ù //
//----------------------------------//

//////////////////////////////////////
// ¼±Çàó¸® Áö½ÃÀÚ
#include // printf(), scanf(), gets()
#include // atoi()
#include // getch()


//////////////////////////////////////
// »ç¿ëÀÚ Á¤ÀÇ ÀÚ·áÇü ¼±¾ðºÎ
typedef unsigned int UINT;


//////////////////////////////////////
// Àü¿ªº¯¼ö ¼±¾ðºÎ
UINT InputValue, // »ç¿ëÀÚ°¡ ÀÔ·ÂÇÑ Á¤¼ö ÀúÀå
OutputValue=1; // ó¸® °á°ú ÀúÀå


//////////////////////////////////////
// ÇÔ¼ö ¼±¾ðºÎ
void Input(void); // »ç¿ëÀÚÀÇ ÀÔ·ÂÀ» ó¸®ÇÏ´Â ÇÔ¼ö
void Factorial(UINT); // ÆÑÅ丮¾óÀ» °è»êÇÏ´Â ÇÔ¼ö
void Output(void); // °è»êµÈ °á°ú¸¦ Ãâ·ÂÇÏ´Â ÇÔ¼ö


//////////////////////////////////////
// ÇÔ¼ö Á¤ÀǺÎ
void Input(void)
{
// »ç¿ëÀÚÀÇ ÀԷ ó¸®
char InputStr[3];
printf("\n\n\t\t ÆÑÅ丮¾ó °è»êÇÒ Á¤¼ö¸¦ ÀÔ·ÂÇϽÿÀ : ");
gets(InputStr); // ÀÔ·Â Á¤¼ö¸¦ ¹®ÀÚ¿­·Î ÀԷ¹ޱâ
InputValue = atoi(InputStr); // ¹®ÀÚ¿­À» Á¤¼ö·Î º¯°æÇϱâ

// ¹æ¾î ÇÁ·Î±×·¡¹Ö
while (InputValue < 1)
printf("\n\t\t ÀÔ·Â ¿À·ù !!! ÀÚ¿¬¼ö¸¦ ÀÔ·ÂÇϽÿÀ : "),
gets(InputStr),
InputValue = atoi(InputStr);
}

void Factorial(UINT n)
{
// ¹æ¾î ÇÁ·Î±×·¡¹Ö
if (InputValue == 1) return;

if (InputValue > 12) // 13! ºÎÅÍ´Â Á¤¼öÇü ÀÚ·á¿¡ ÀúÀå ºÒ°¡
{
OutputValue = 0;
return;
}

// ¹Ýº¹ °è»ê ¾Ë°í¸®ÁòÀ» ÀÌ¿ëÇÑ °è»ê
for (UINT i=2; iOutputValue *= i;
}

void Output(void)
{
// °è»ê °á°ú Ãâ·Â
printf("\n\n\t\t °è»ê °á°ú : %d! = %d", InputValue, OutputValue);

// »ç¿ëÀÚÀÇ È®ÀÎ
printf("\n\n\n\t\t Press Any Key To Exit ...");
getch();
}


//////////////////////////////////////
// ¸ÞÀÎÇÔ¼ö Á¤ÀǺÎ
void main(void)
{
Input();
Factorial(InputValue);
Output();
}





#include
main()
{

int limit;
int factorial;
int i;

printf("\n±¸ÇÏ°íÀÚ ÇÏ´Â factorial (ÀÔ·Âex:1~10) : ");
scanf("%d",&limit);
factorial = 0;
for (i=limit;i>=1;i--){

factorial = factorial * i;

}

printf("%d! = %ld\n",limit, factorial);
return 0;
}



ÀÚ ^^ ÀÏ´Ü Àú·¸°Ô Å«°Ç ÇÊ¿ä°¡ ¾ø°í¿ä..

¿ø·¡ ÆÑÅ丮¾óÀÌ

10! À̶ó¸é 10x9x8x7x6x5x4x3x2x1 À̱⠶§¹®¿¡

±ò²ûÇÏ°Ô for¹®ÀÌ ^^

±×¸®°í Ãâ·Â¹®ÀÌ ¿©·¯°³ ³ª¿À´Â°Ç whil¹® ¾ÈÂÊ¿¡ ½è±â ‹š¹®ÀÔ´Ï´Ù ^^

±×¸®°í int Çüµµ ºñÁÖ¾ó C++¿¡¼­´Â ¸Þ¸ð¸®¿¡¼­ Å©°Ô ÀâÈ÷±â ¶§¹®¿¡.. ¾Æ¸¶ 9ÀÚ¸®Àΰ¡ 11ÀÚ¸®Àΰ¡±îÁö Áö¿øµÉ²®´Ï´Ù..

±×·¯¹Ç·Î unsigned long ±îÁö´Â ¾È°¡µµ µË´Ï´Ù ^^

µ¥ÀÌÅÍ°¡ 10¹Û¿¡ ¾ÈµÇÀÚ³ª¿ä ^^;;







//1¿¡¼­ 10»çÀÌÀÇ ¾çÀÇ Á¤¼ö(n)À» ÀÔ·Â¹Þ¾Æ n!(factorial)À» ±¸ÇÏ´Â ÇÁ·Î±×·¥À»
//ÀÛ¼ºÇÏ´Â °ÍÀÔ´Ï´Ù.(Á¶°ÇÀº for,while,do~while¹®À» ÀÌ¿ë)

#include
main()
{
unsigned long limit ;
unsigned long factorial = 1;
int i;

printf("\n±¸ÇÏ°íÀÚ ÇÏ´Â factorial (ÀÔ·Âex:1~10) : ");
scanf("%d",&limit);

i = 1;
while (i<=limit)
{
factorial *= i;
printf("%d! = %ld\n",limit, factorial);
}

return 0;
}

Á¦ÀÏ ³­°¨ÇÑ°Ô¿ä ÇϳªÀÇ Á¤¼ö¸¦ ÀÔ·Â ¹Þ¾Æ¼­ ±× °ª¿¡ ÇØ´çµÇ´Â ÆÑÅ丮¾ó °ªÀÌ ³ª¿À°Ô Çϴ°ǵ¥ ¾î¶»°Ô ÇØ¾ß µÉÁö ¤Ñ¤Ñ ³Ñ º¹ÀâÇÕ´Ï´Ù



ÆÑÅ丮¾ó °è½Â À̶õ?

ÆÑÅ丮¾ó À» »ç¿ëÇÏ¸é ´õ Å« ÀÚ¸®ÀÇ °á°ú°ªÀ» ³ªÅ¸³¾¼ö ÀÖ´Ù.





#include
#include
using namespace std;

int main()
{
vector* vecData = new vector;

int length = 40000; // °á°ú°ªÀÇ ÀÚ¸®¼ö

vecData->reserve(length);
vecData->assign(length, -1);
int n = 1000;
int carry = 0;

(*vecData)[0] = 1;
int offset = 1;
for(int i=2;i <= n;i++){
for(int j=0;j < offset;j++){
(*vecData)[j] = (*vecData)[j] * i + carry;
carry = 0;
if((*vecData)[j] > 9){
if((*vecData)[j+1] == -1){
offset++;
(*vecData)[j+1] = 0;
}
carry = (*vecData)[j] / 10;
(*vecData)[j] = (*vecData)[j] % 10;
}
}
}

for(int i=0;i < offset;i++){
cout << (*vecData)[offset-i-1];
}

delete vecData;
return 0;
}




///////////////////////////////////////////////////////////////////////////



Source Code

#include

int factorial(int);

void main(void) {
int number;

cout << "Please enter a positive integer: ";
cin >> number;
if (number < 0)
cout << "That is not a positive integer.\n";
else
cout << number << " factorial is: " << factorial(number) << endl;
}

int factorial(int number) {
int temp;

if(number <= 1) return 1;

temp = number * factorial(number - 1);
return temp;
}
////////////////////////////////////////////////////////////////////////////////////


http://groups.engin.umd.umich.edu/CIS/course.des/cis400/cpp/factorial.html


http://groups.engin.umd.umich.edu/CIS/course.des/cis400/cpp/factorial.html


Reference:

http://en.wikipedia.org/wiki/Recursion_(computer_science)



Mastering recursive programming



http://www.ibm.com/developerworks/linux/library/l-recurs.html