Recursion
Computer Engineering / Algorithm
2 minutes read (About 272 words)

Recursion

Recursion (재귀)

  1. 함수 호출 도중에 자기 자신을 다시 호출하는 것

  2. Base case가 필수 (기초, 종료, 탈출 조건)

    Base case가 없으면 무한으로 자기 자신을 호출해서 stack overflow가 된다.

재귀함수를 만드는 방법

  1. 패턴을 찾는다. 즉, 점화식(Induction)을 만든다.
  2. Base case를 만든다.

예제1: Factorial !

  • Basis

    0! = 1! = 1

  • Induction Step

    n! = (n-1) * (n-2) * (n-3) * … 3 * 2 * 1

1
2
3
4
5
def factorial(n):
    if n <= 1:
        return 1
    else:
        return n*factorial(n-1)

예제2: Fibonacci

  • Basis

    fib(0) = fib(1) = 1

  • Induction Step

    fib(n) = fib(n-1) + fib(n-2)

1
2
3
4
5
def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Fibonacci Dynamic Programming

  1. Memorization (Top Down)
1
2
3
4
5
6
7
8
9
f = [-1 for _ in range(100)]
def fib_memorize(n):
    if f[n] > -1:
        return f[n]
    elif n <= 1:
        f[n] = 1
    else:
        f[n] = fib_memorize(n-1) + fib_memorize(n-2)
    return f[n]
  1. Bottom Up
1
2
3
4
5
6
f2 = [-1 for _ in range(100)]
def fib_bottup(n):
    f2[0] = f[1] = 1
    for i in range(2, n+1):
        f[n] = f[n-1] + f[n-2]
    return f[n]

예제3: Hanoi Tower

Play Tower of Hanoi

1
2
3
4
5
6
7
8
def hanoi(n, _from, _by, _to):
    # base case
    if n==1:
        print(f'{n}번째 쟁반을 {_from}에서 {_to}로 옮긴다.')
        return
    hanoi(n-1, _from, _to, _by)
    print(f'{n}번째 쟁반을 {_from}에서 {_to}로 옮긴다.')
    hanoi(n-1, _by, _from, _to)
Follow

Links

Tag Cloud

ADT Abstraction Access Modifier Ajax Algorithm Angluar Angular Array Babel C C# Call by Object Reference Call by Reference Call by Value Class Computational Thinking DOM Data Type Dependency Injection Destructuring ECMA ES6 Encapsulation Event Expression FDS12 First-class object Fisrt-class Function Function HTML, CSS Hackaton Higher Order Function Hoisting Inheritance Math Modlue Node.js Number OOP Object Observable Operater Pipe Polymorphisim Programming Promise Prototype Python Quick sort REST API React Reactive Programming Recursion RegExp Routing SPA Scope Service Single Page Application Statement String Subsequence Substring TIL TypeScript Unity Variable Web Browser Webpack Wrapper global variable immutable javaScript local variavble mutable npm object pass by reference pass by value primitive this window 실행 컨텍스트 일급 객체 자바스크립트

Categories

Recent

Archives

Tags

ADT 1
Abstraction 2
Access Modifier 1
Ajax 1
Algorithm 18
Angluar 1
Angular 10
Array 1
Babel 1
C 1
C# 1
Call by Object Reference 1
Call by Reference 1
Call by Value 1
Class 2
Computational Thinking 1
DOM 1
Data Type 1
Dependency Injection 1
Destructuring 1
ECMA 1
ES6 1
Encapsulation 2
Event 1
Expression 1
FDS12 2
First-class object 1
Fisrt-class Function 1
Function 1
HTML, CSS 5
Hackaton 2
Higher Order Function 1
Hoisting 1
Inheritance 1
Math 1
Modlue 1
Node.js 2
Number 1
OOP 3
Object 1
Observable 1
Operater 1
Pipe 1
Polymorphisim 1
Programming 1
Promise 1
Prototype 1
Python 5
Quick sort 1
REST API 1
React 1
Reactive Programming 1
Recursion 1
RegExp 1
Routing 2
SPA 1
Scope 1
Service 1
Single Page Application 1
Statement 1
String 1
Subsequence 1
Substring 1
TIL 85
TypeScript 2
Unity 1
Variable 1
Web Browser 1
Webpack 1
Wrapper 1
global variable 1
immutable 1
javaScript 2
local variavble 1
mutable 1
npm 1
object 1
pass by reference 1
pass by value 1
primitive 1
this 1
window 1
실행 컨텍스트 1
일급 객체 1
자바스크립트 39

Categories

Recent

Archives

Tags

ADT 1
Abstraction 2
Access Modifier 1
Ajax 1
Algorithm 18
Angluar 1
Angular 10
Array 1
Babel 1
C 1
C# 1
Call by Object Reference 1
Call by Reference 1
Call by Value 1
Class 2
Computational Thinking 1
DOM 1
Data Type 1
Dependency Injection 1
Destructuring 1
ECMA 1
ES6 1
Encapsulation 2
Event 1
Expression 1
FDS12 2
First-class object 1
Fisrt-class Function 1
Function 1
HTML, CSS 5
Hackaton 2
Higher Order Function 1
Hoisting 1
Inheritance 1
Math 1
Modlue 1
Node.js 2
Number 1
OOP 3
Object 1
Observable 1
Operater 1
Pipe 1
Polymorphisim 1
Programming 1
Promise 1
Prototype 1
Python 5
Quick sort 1
REST API 1
React 1
Reactive Programming 1
Recursion 1
RegExp 1
Routing 2
SPA 1
Scope 1
Service 1
Single Page Application 1
Statement 1
String 1
Subsequence 1
Substring 1
TIL 85
TypeScript 2
Unity 1
Variable 1
Web Browser 1
Webpack 1
Wrapper 1
global variable 1
immutable 1
javaScript 2
local variavble 1
mutable 1
npm 1
object 1
pass by reference 1
pass by value 1
primitive 1
this 1
window 1
실행 컨텍스트 1
일급 객체 1
자바스크립트 39
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×