[Algorithm/알고리즘] Exercise 2: Recursion(재귀)

Task 1

1.1. Analyse the algorithm RecursiveAlgo in the program WhatdoIdo. Explain what the algorithm does and what it returns if it is executed.

주어진 racecar로 알고리즘을 분석해보자.

처음 RecursiveAlgo(str, 0, 6)을 실행하면 str[0] = r, str[6] = r이므로 RecursiveAlgo(str, 1, 5)를 호출하게 된다.

RecursiveAlgo(str, 1, 5)을 실행하면 str[1] = a, str[5] = a이므로 RecursiveAlgo(str, 2, 4)를 호출하게 된다.

RecursiveAlgo(str, 2, 4)을 실행하면 str[2] = c, str[4] = c이므로 RecursiveAlgo(str, 3, 3)를 호출하게 된다.

RecursiveAlgo(str, 3, 3)을 실행하면 3==3이므로 true를 리턴한다.

 

이렇게 보면 이 알고리즘은 주어진 문자열이 좌우대칭형인지를 판단하는 것이다.

그런데 이걸 영어로 어떻게 적니..?^^

 

정답: The program tests if a string (array of characters) is a palindrome i.e. it uses recursion to check if a word is read the same forward and backwards.

 

palindrome은 회문이란 뜻이다. 

참고로 좌우대칭은 bilateral symmetry이라고 한다.

 

 

1.2. What is the time complexity of the algorithm. Assume that the input has length n.

이 알고리즘의 시간복잡도는 n/2의 내림이다. 따라서 O(n)에 해당한다.

 

 

Task 2

Analyse the function printRec(int n) and answer the following questions.

 void printRec(int n) {
  if (n == 0)
    return;
  printf("%d", n%2); //%는 나머지
  printRec(n/2);
}

 

2.1. What is the output of the function call printRec(20)?

n=20: printf(0); printRec(10);

n=10: printf(0); printRec(5);

n=5: printf(1); printRec(2);     // 5/2는 2.5이지만 n은 int이므로 2가 된다

n=2: printf(0); printRec(1);

n=1: printf(1); printRec(0);

n=0: return

따라서 00101이라는 결과가 나온다.

 

2.2. Write down the sequence of recursive function calls and the respective arguments for the call to printRec(20)?

위에 적었다 :)

 

2.3. To get the output 10100 for n = 20 using the function printRec(n), which changes would you made in the function printRec(n)?

printf와 printRec의 순서를 바꾸면 된다.

 void printRec(int n) {
  if (n == 0)
    return;
  printRec(n/2);
  printf("%d", n%2); //%는 나머지
}

 

 

Task 3

The Tower of Hanoi is a game consisting of three pegs and a number of disks that can be placed on any of the pegs. No two disks have the same size. At the beginning all disks are stacked on the first peg in order of decreasing size (the smallest disk at the top). The goal of the game is to move all disks to the second peg. In each step only the top-most disk from a peg can be moved to the top of another peg. A large disk may never be placed on top of a smaller disk. The picture below illustrates the stacks for a game with seven disks after 4 moves.

Implement the solution of the Tower of Hanoi game with up to nine disks in C. It shall be possible to choose the number of disks and to display the stacks in a terminal after a given number of moves. Display the stacks for 8 disks after 213 moves.

 

드디어 올 게 왔다. 하노이의 탑...

참고로 하노이의 탑에 대한 설명은 아래글을 참고했다.

하노이의 탑을 처음 접한다면, 먼저 칸 아카데미 사이트에서 제공되는 게임으로 어떤 느낌인지 체득해보면 좋을 것 같다.

그리고 아래 깃허브에서 어떻게 문제 해결에 접근해야 하는지 답을 얻을 수 있다.

 

하노이의 탑 (개념 이해하기) | 알고리즘 | Khan Academy

'하노이의 탑' 이해하기

 

이거는 나중에 추가 예정ㅜㅜ

 

 

Task 4

Write a recursive function that takes in an integer array of length n and recursively reduces the array by adding two neighbouring numbers. Each new array array is stacked on top of the previous array. Thus, the output is a pyramid in which each element i is the sum of the left and right child of the element i in the level below as depicted below for the case A = [5, 4, 6, 1, 3].

#include <stdio.h>

void make_triangle (int A[], int n, int level) {
  // terminating
  if (n==0) {
    return; //이기 때문에 void를 사용
  }

  // recursive case
  int t[n-1];
  for (int i=0; i<n-1; i++) {
    t[i] = A[i] + A[i+1];
  }

  // recursive function call
  make_triangle(t, n-1, level+1);

  // margin depending on the level
  for (int j=0; j<=level; j++) {
    printf(" ");
  }

  // print current array A[]
  for (int j=0; j<n; j++) {
    if (A[j]<10) { // 두자리수 맞춤
      printf("%d  ", A[j]);
    } else {
      printf("%d ", A[j]);
    }
  }
  printf("\n");
}

int main() {
  int A[] = {5,4,6,1,3};
  make_triangle(A, 5, 1);
}

 

이렇게 실행하면 아래와 같은 결과가 나온다.

 

      64 
     36 28
    19 17 11
   9  10 7  4
  5  4  6  1  3

 

exercise 하나 끝내는 데 천만 년 걸린다..^^....