1. what is recursion
2. Example of Recursion
3. tracing recursion
4. stack used in recursion
5. time complexity
6. recurrence relation

what is recursion

• 로컬 함수 스스로 cycling 하는 것.
  • 스프링이라 생각하면 된다.
  • 땡겨서 정확한 index 데이터 값을 찾는데 주로 쓰인다.
• they are two method in recursion(Tail recursion, Head Recursion)

Recursion 하기 전에 print out(Tail Recursion)

void fun1(int n)
{
  if(n>0) // 1 unit
  {
    cout<<n; // 1 unit
    fun1(n-1); // func1(n-1)
  }
}
int main()
{
  int x = 3;
  fun1(x);
}

Recursion이후 print out(Head Recursion)

void fun1(int n)
{
  if(n>0) // 1 unit
  {
    fun1(n-1); // func1(n-1)
    cout<<n; // 1 unit
  }
}
int main()
{
  int x = 3;
  fun1(x);
}

• 연속적으로 연결되어있는 (like tail) 방이 있는데 안쪽에서 부터 불을 끌것이냐, 들어가면서 불을 끌것이냐 와 같은 문제이다.

• 들어가면서 불을 끌껏이다
  • Recursion 하기 전에 print out 방법(Tail recursion)
• 나오면서 불을 끄겟다
  • Recursion이후 print out(Haed Recursion)
• 이것을 더 정확하게 말하자면 Recursive functions에서는 두가지 calling 방법이 있는데
  • Ascending
  • Descending 이다.

void fun(int n)
{
  if(n>0) // 1 unit
  {
    1.____ // calling (ascending 방법)
    2. fun(n-1);
    2.____ // returning (Descending 방법)
  }
}

Time Complexity

• Calling n+1 time 이므로, O(n) 이다

• Time complex를 조건부로 쓰자면

  • n=0 일 경우, Time complex of fun(n) =1
  • n>0 일 경우, time complex of fun(n) = fun(n-1)+1 = O(n)

Static or Global variables in Recursion

Static vairblae in Recursion

#include <stdio.h>
int fun1(int n)
{
 static int x=0; //static variable
 if(n>0)
 {
 x++;
 return fun(n-1)+x;
 }
 return 0;
}
int main() {
 int r;
 r=fun1(3);
 printf("%d\n",r); // output 9

 r=fun1(3);
 printf("%d\n",r); // output 18

 return 0;
}

• static variable는 local function이 종료가 되도 value가 남아 있다. 다만 오직 local function에서만 사용할 수 있고 다른 함수에서는 사용 할 수없다

Global varibale in Recursion

#include <stdio.h>
int x=0; // global variable
int fun(int n)
{
 if(n>0)
 {
 x++;
 return fun(n-1)+x;
 }
 return 0;
}
int main() {
 int r;
 r=fun(3);
 printf("%d\n",r);

 r=fun(3);
 printf("%d\n",r);

 return 0;
}

• 반면에 Global varible 같은 경우에는 값이 항상 유지 남아 있고 다른 function에도 사용할 수 있다.

Tree Recursion.

#include <stdio.h>
void fun(int n)
{
 if(n>0)
 {
 printf("%d ",n);
 fun(n-1);
 fun(n-1);
 }
}
int main() {
 fun(3);
 return 0;
}

// output : 3 2 1 1 2 1 1

• Tail Recursion 뒤에 또다른 Tail Recursion을 넣은 방법.

• time complexcity O(2^n)
  • 2^0 + 2^1 + 2^2 ….
• Space complexity O(n)

  Indirect Recursion

#include <stdio.h>
void funB(int n);
void funA(int n)
{
 if(n>0)
 {
 printf("%d ",n);
 funB(n-1);
 }
}
void funB(int n)
{
 if(n>1)
 {
 printf("%d ",n);
 funA(n/2);
 }
}
int main()
{
 funA(20);
 return 0;
}
// output 20 19 8 4 3 1

• 자기 자신을 Recursion 즉 circle 하는 것이 아닌, 다른 함수와 Link하여서 Recursion 방법으로 사용할 수있는 방법 (Indirect Recurion)

Nested Recursion

• Recursion Function 안에 한번 더 Recursion Function 하는 것

#include <stdio.h>
int fun(int n)
{
 if(n>100)
 return n-10;
 return fun(fun(n+11));
}
int main()
{
 int r;
 r=fun(95);
 printf("%d\n",r);
 return 0;
}
// output 91