Algorithm - Recursion 1


 

Algorithm - Recursion 1

Recursion

Recursion ( 재귀, 점화, 귀납) in Mathematics

어떤 수학적인 함수를 정의함에 있어, 함수의 정의를 이용하여 정의하는 것.

Recursion (재귀) in Computer Science

프로그램에서 함수에서 직-간접적으로 자기 자신 함수를 호출하는 것.

많은 문제를 해결하는 가장 효율적인 알고리즘을 개발하는데 사용된다.

- 분할 정복 기법(Divide & Conquer), 동적 계획법(Dynamic Programming), 백 트래킹(Back tracking)

base case

The part of a recursive definition or algorithm that is not defined in terms of itself.

Recursive 에서 직접 함수 계산할 수 있는 경우

recursive step

직접적으로 계산할 수 없어, 회귀적 으로 base case가 만들어 질 때 까지 호출하면서 계산하는 단계이다.

Recursion Type

1. Unary recursion

single recursive call 단일 호출로 

factorial, linear sum, reversing array, computing powers 등이 있다.

2. Binary

two recursive call 두 번 호출로

Fibonacci numbers, Hanoi tower, merge sorting, quick sorting 등이 있다.

3. Multiple Recursion

more than two recursive call 세 번 이상의 호출이 이루어진다.

flood fill, knight’s tour

Call stack

실행할 컴퓨터 프로그램 코드 정보를 저장하는 스택 자료구조이다. 또한 실행 스택(execution stack), 제어 스택 (control stack), 런 타임 스택(run-time) 스택 혹은 기계 스택 (machine stack) 이라고도 하며 그냥 줄여서 스택 (the stack) 이라고도 한다. 소프트웨어 프로그램의 기능 수행에 있어 콜 스택의 유지 보수가 중요함에도 불구하고 구현 상세는 고급 프로그래밍 언어에서는 보통 감추어지며 자동화되어 있다.

콜 스택은 몇 가지 목적을 위해 이용할 수 있다. 하지만 콜 스택이라는 걸 사용하는 주 이유는 현재 실행 중인 서브루틴을 실행한 다음 어디로 돌아가야 할지 그 절차들을 따라가기 위함이다. 실행 중인 서브루틴은 이제 막 호출되었으나 명령을 전부 끝나치기 전에도 다른 호출에 의해 또 다른 서브루틴으로 넘어가버릴 수도 있다. 이러한 서브루틴의 행동은 (재귀나 기타 특별한 경우를 처리할 때) 수많은 단계를 따라 저장된다.

stack overflow

스택 포인터가 스택의 경계를 넘어설 때 일어난다. 호출 스택은 제안된 양의 주소 공간을 이루며 대개 프로그램 시작 시 결정된다.

프로그램이 호출 스택(call stack)에서 이용 가능한 공간 이상을 사용하려고 시도할 때, 스택이 오버플로(overflow)된다고 하며 이 경우 일반적으로 프로그램 충돌이 발생하게 된다.

Recursion EX.

Factorial

iterator pattern

int factorial_iterator(int n) { int i, factorial =1; for(i=1; i<=n; i+=) factorial *= 1; return factorial; }

recursive pattern

int factorial_recursive(int n) { if(n == 1) // base case return 1; else return n*factorial_recursive(n-1); }

Linear Sum

n 개의 정수가 주어졌을 때, 그 정수의 합을 계산한다.

iterator pattern

int sum_iterator(int array[], int n) { int i, sum=0; for(i=0; i<n; i++) sum += array[i]; return sum; }

recursive pattern

int sum_recursive(int array[], int n) { if(n == 0) //base case return array[0]; else //recursive step return sum_recursive(array,n-1)+array[n-1]; }

Reversing Array

배열 전체 요소를 정반대로 위치한다.

iterator pattern

void reversing_array_iterator(int array[], int n) { int head, tail=n; do{ swap(array,head,tail); head++; tail--; }while(head > tail) }

recursive pattern

void reversing_array_recursive(int array[], int head, int tail) { // base, recursive step if(head < tail) { swap(array, head, tail); reversing_array_recursive(array,head+1,tail-1) } }

computing power

x에 n승

iterator pattern

double power_iterator(double x, int n) { int i; double power = 1.0; for(i=1;i<=n;i++) power *= x; return power; }

recursive pattern -1

다음의 base operation은 x*power(x,n-1)로 곱셈(multiplication) 연산으로

Complexity는 O(n)입니다.

double power(double x, int n) { if(n == 0) // base case return 1.0; else return x*power(x,n-1); }

recursive pattern -2

Fast Computing Powers

double squaring 제곱을 2*n으로 표기합니다.

even(짝수)와 odd(홀수)일 경우로 나뉘게 됩니다.

double fastPower_recursive(double x, int n) { double y; if(n == 0) // base caes; return 1.0; else if(n % 2 == 1) { // odd y = p(x, (n-1)/2); return x*y*y; }else { // even y = p(x, n/2); return y*y; } }