재귀

1. 기본

재귀가 무한루프에서 빠지지 않으려면
base case     :  적어도 하나의 recursion에 빠지지 않는 경우가 존재해야합니다.
recursion case :  recursion을 반복하다 보면 결국 base case로 수렴해야합니다.

자바스크립트 코드 입니다.

const fun = function(n){
    if(n<1){
        //base case 
        return;
    }else{
        //recursion case
        console.log("hello");
        fun(--n);
    }
}
fun(3);

 

 

 

 

2. 패턴사용.

2-1. 컴포지트패턴으로 만들어 봤습니다.

const Number = class{
    constructor(data){
        this._data = data;
        this._next = null;
    }
    getNext(){
        return this._next;
    }
    setNext(number){
        this._next = number;
    }
    execute(){
        console.log(`hello ${this._data}`)
    }
}

const Rec = class{
    constructor(){
        this._head = null;
    }

    addFirst(data){
        const newNumber = new Number(data);
        newNumber.setNext(this._head);
        this._head = newNumber;
    }

    hello(){
        this._hello2(this._head);
    }

    _hello2(number){
        if(number){
            number.execute();
            const n = number.getNext();
            this._hello2(n);
        }
    }
}

const rec = new Rec();
rec.addFirst(1);
rec.addFirst(2);
rec.addFirst(3);

rec.hello();

 

2-2. 재귀적으로 합산하는 기능을 넣어 봤습니다.

addLast기능도 추가했습니다.

const Number = class {
  constructor(data) {
    this._data = data;
    this._next = null;
  }
  getNext() {
    return this._next;
  }
  setNext(number) {
    this._next = number;
  }
  sum() {
    if (this._next) 
			return this._data + this._next.sum();
    else
			return this._data;
  }
};

const Rec = class {
  constructor() {
    this._head = null;
  }

  addFirst(data) {
    const newNumber = new Number(data);
    newNumber.setNext(this._head);
    this._head = newNumber;
  }

  addLast(data) {
    const newNode = new Number(data);
    if (this._head == null) {
      this._head = newNode;
      return;
    }
    let p = this._head;
    while (p.getNext() != null) {
      p = p.getNext();
    }
    p.setNext(newNode);
  }

  sum() {
    return this._head.sum();
  }
};

const rec = new Rec();

let n = 6;
while (n--) {
  rec.addLast(n);
}

console.log(rec.sum());