[Algorithm] Recursion 재귀

Recursion (재귀)

Recursion은 자기자신을 호출하는 알고리즘이다. 피보나치 수열 또는 팩토리얼(factorial)에 활용할 수 있다.

Recursive vs. Iterative

Recursive 호출과 Interaive 호출을 비교해보자.
Recursive는 base 값을 찾아 x_base를 반환하기 전까지 자기자신을 계속 호출한다.
Iterative는 x_base를 초기 값으로 하여 1을 증가시키며 factorial 연산 f에 i와 x를 for loop이 반복될 때마다 계산해서 값을 얻는다.

Recursive Case

$x_n = f(n, x_{n-1})$ from $x_{base}:$

function recursive(n):
	if n== base
    	return  x_base 
   	else
    	returnf(n, recursive(n-1))

Interative Case

function iterative(n) : 
    x = x_base
    for i = base+1 to n
        x = f(i, x)
    return x

Applications of Recursion Algorithm

• Tree
• Graph Traversal
• Towers of Hanoi
• Divide and Conquer Algorithms
• Merge Sort
• Quick Sort
• Binary Search.

Example

Factorial example을 보겠다.

public class Factorial {
   public static long factorial(int n) {
      if (n <= 1)
         return 1;
      else
         return n * factorial(n - 1);
   }
   
   public static void main(String args[]) {
      System.out.println("The factorial of 5 is: " + factorial(5));
   }
}

코드를 호출하면, 순서대로 아래 표와 같이 된다.

call	fcatorial(5)
call	5*factorial(5-1)
call	4*factorial(4-1)
call	3*factorial(3-1)
call	2*factorial(2-1)
call	1*factorial(1-1)
return  1
return	2*1
return	3*(2*1)
return	4*(3(2*1))
return	5*(4*(3*(2*1))

>>120

Reference

[1] https://en.wikipedia.org/wiki/Recursion_(computer_science)
[2] https://www.geeksforgeeks.org/what-is-the-difference-between-backtracking-and-recursion/?ref=lbp
[3] https://www.geeksforgeeks.org/recursion-algorithms/?ref=lbp
[4] https://www.tutorialspoint.com/recursive-factorial-method-in-java