Algorithm - 재귀함수/호출 연습 (recursion practice)

문제 1) 재귀함수를 이용하여 1부터 n까지의 곱셈을 구현하라. 

 

1) for문을 이용한 코드

def multiple(num):
    return_value = 1
    for index in range(1, num+1):
        return_value = return_value * index
    return return_value

 

 

[결과]

 

 

2) 재귀함수를 이용한 코드

def multiple(num):
    if num <= 1:
        return num
    else:
        return num * multiple(num-1)

 

 

[결과]

 

 

문제 해설) multiple(3) 수행

1) multiple(3) 수행 

- 3은 1보다 크기 때문에 else문 수행

→ 3 x multiple(2)

 

2) multiple(2) 수행 

- 2는 1보다 크기 때문에 else문 수행 

→ 2 x multiple(1) 

 

3) multiple(1) 수행 

- 1은 if문에 걸려서 num을 반환

→ 1   

 

이 과정을 하나로 정리하여 생각해 보면, 

3 x multiple(2) == 3 x 2 x multiple(1) == 3 x 2 x 1 이 되는 것이다. 

 

그러므로 식을 모두 합쳐서 생각해보면 3 * 2 * 1 즉, 6이라는 값이 반환된다. 

---

문제 2) 숫자가 들어있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수를 구현하라

 

1) for문을 이용한 코드

def total(data_list):
    total_value = 0
    for index in range(len(data_list)):
        total_value += data_list[index]
    return total_value

 

 

[결과]

 

 

2) 재귀함수를 이용한 코드

def total(data_list):
    if len(data_list) <= 1:
        return data_list[0]
    else:
        return data_list[0] + total(data_list[1:])    

 

 

[결과]

---

문제 3) 회문(Palindrome)을 판단하는 함수를 재귀용법으로 구현하라

* 회문이란? 거꾸로 읽어도 동일한 단어 또는 문장 ex) level 

def palindrome(word):
    if len(word) <= 1:
        return True
    else:
        if word[0] == word[-1]:
            return palindrome(word[1:-1])
        else:
            return False

 

[결과]

---

문제 4) 아래의 조건을 기반으로 재귀함수를 이용해 구현하라

a) 정수 n이 있다.

b) n이 홀수이면 → 3 x n + 1 수행c) n이 짝수이면 → n/2 수행 d) 이를 반복하여 n이 결국 1이 될 때까지의 과정을 모두 출력하는 재귀함수를 구현하라 

 

def calculation(num):
    print(num)
    if num == 1:
        return num
    else:
        if num % 2 == 0:
            return calculation(int(num / 2))
           
        else:
            return calculation(int(3 * num + 1))

 

 

[결과]

---

문제 5) 아래의 조건을 기반으로 재귀함수를 이용해 구현하라

- 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있다.

 

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

 

- 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오

 

 

[규칙성 찾기]

 

ex) 1

1

→ 1가지

 

ex) 2

1 + 1

2 

→ 2가지

 

ex) 3

1 + 1 + 1

2 + 1

1 + 2

3

→ 4가지 

 

ex) 4

1 + 1 + 1 + 1

2 + 1 + 1

1 + 2 + 1

1 + 1 + 2

2 + 2

3 + 1 

1 + 3 

→ 7가지 

 

가지수의 변화는 1 → 2 → 4 → 7 이다. 여기서 1 + 2 + 4를 하면 7이 나온다는 규칙성을 발견할 수 있다. 이를 코드로 구현하면 된다. 

 

def func(data):
    if data == 1:
        return 1
    elif data == 2:
        return 2
    elif data == 3:
        return 4
    
    return func(data - 1) + func(data - 2) + func(data - 3)

 

[결과]

 

 

문제해설) func(4) , func(5) 풀이 

 

1) func(4)

- if문에 걸리지 않기 때문에 맨 아래의 return문을 수행한다.

- func(3) + func(2) + func(1) == 4 + 2 + 1 == 7

 

2) func(5) 

- if문에 걸리지 않기 때문에 맨 아래의 return문을 수행한다.

- func(4) + func(3) + func(2) == 7 + 4 + 2 == 13