Swift (스위프트) 재귀함수 - 등차급수, 등비급수, 팩토리얼

2020. 4. 4. 12:15

재귀함수의 이해

기본 실습. "Hello"를 하나씩 붙여가며 "Hello Politech"을 반복해서 출력하자.

func showHellow(name: String, n:Int)	// 입력 받은 파라미터로부터 name:String = "Politech", n:Int = 0 을 넣고 함수를 돌린다. 다음번 재귀함수때는 이번 함수가 리턴하는 파라미터를 넣고 돌린다.
{
    // 탈출조건을 맨 앞에 쓴다.
    if n > 5 {
        return
    }
    let mystr:String = "Hello \(name)"
    print(mystr)
    var myn = n + 1     // 인풋 파라미터는 함수 내에서 상수라 바꿀 수 없다.
    
    showHellow(name: mystr, n: myn)   // 외부에서 들어온 파라미터를 그대로 넘겨줄 필요는 없다. 인풋 파라미터가 상수라는건 그 함수 내에서 상수란거지, 여기서는 다음번 재귀함수에 넘겨줄 새로운 파라미터니까 얼마든지 다른것을 보낼 수 있다. 다음번 재귀함수로 넘겨줄 파라미터를 다른 것으로 변경하고싶다면 처음 함수에서 다시 재귀함수를 호출하기 전, 즉 이 위에 새 파라미터로 이용할 변수들을 선언하면 된다.
}

showHellow(name: "Politech", n: 0)

결과 :
Hello Politech
Hello Hello Politech
Hello Hello Hello Politech
Hello Hello Hello Hello Politech
Hello Hello Hello Hello Hello Politech
Hello Hello Hello Hello Hello Hello Politech

//더 간단하게 반복 횟수를 직관적으로 입력해서 출력하도록 바꿀 수도 있다.

func showHellow(name: String, n:Int)
{
    // 탈출조건을 맨 앞에 쓴다.
    if n == 0 {
        return
    }
    let mystr:String = "Hello \(name)"
    print(mystr)
    showHellow(name: mystr, n: n-1)
}

showHellow(name: "Politech", n: 6)

제자리로 돌아가 함수가 완전히 복제된다는 개념으로 이해하고 사용하려 하면 변수는 매번 초기화 되고, 매번 자기자신 그대로 복제되기만 해서 무한루프에 빠질 뿐이다. (닥터 스트레인지의 시간에 갇힌 도르마무처럼...)

이는 개념을 잘못 이해한 부분으로 평행우주와 같은 개념으로 이해해야한다.. 같은 세상(Function)이지만 이 세상의 나(Parameter)와 다른 평행 우주에 있는 나(Parameter')는 다르다. 이렇게 재귀함수를 100번 반복한다 했을 때 내 세상에서 나는 여러 평행우주의 세상 중 하나로 이어지고, 그 평행우주의 세상의 또 다른 내가 다른 평행우주의 세상 중 하나로 이어지고 이렇게 세상(Function)은 같지만 나(Parameter)는 다른 여러개의 평행우주가 이어진다고 생각하면 된다.

재귀함수에서는 절대 파라미터의 이름에 의미를 두지 말자!!

그저 파라미터1, 파라미터2일 뿐이다.

그러면 최초 입력 파라미터와 재귀함수로 넘길 파라미터, 재귀함수에 들어온 파라미터를 혼동할 일이 없다.

변수의 이름에 너무 익숙해져있다보니
'최초 입력 파라미터 = 재귀함수로 넘길 파라미터 = 재귀함수에 들어온 파라미터'
이렇게 잘못 생각해서 문제가 어려워진다.

Quiz 1. 재귀함수로 1 ~ n의 합을 구하는 등차급수 만들기.

// Analysis 1. 100을 입력 받으면 1~100까지 합은 1+2+3+...+99+100
// Analysis 2. 반복문 방식 카운팅 하는 변수와 그 합을 담을 sum이라는 변수 2개가 필요하다. 따라서 사용 불가능하다. 또한 입력 받은 파라미터는 let(상수)로 함수 내부에서 변경이 불가능하다.
// Analysis 3. 재귀함수 내에 다른 변수를 선언하면 그 변수는 재귀함수가 돌 때마다 초기화되어 사용 불가능하다.
// Analysis 4. 리턴으로 내보낼 값은 하나뿐이니 재귀함수의 리턴값에 계산할 수식을 넣어 재귀함수를 이어 붙인다.
// Analysis 5. 1+2+3+...+99+100 은 100+99+...+3+2+1 이니까 입력 받은 수를 1씩 빼면서 재귀함수를 이어 붙인다.


// 내용 : 1부터 입력받은 수까지 합을 구하는 등비급수 함수
// 파라미터 : endNum:Int
// 목적 : 재귀함수를 이용해 등비급수를 구한다.

// Step 1. 입력 파라미터를 정수로 받아 넘긴다.
// Step 2. endNum + (endNum-1) + ... + 3 + 2 + 1 순서로 할꺼니 마지막 1이 나오면 종료하는 조건을 설정한다.
// Step 3. 그 외의 경우에는 리턴에 자기 자신을 -1씩 소환하며 더하는 수식을 적는다.
func arithmeticSeries(endNum:Int) -> (Int) { // Step 1. 입력 파라미터로 정수를 받아 넘긴다.
    if endNum == 1 {    // Step 2. 마지막 입력 파라미터 1이 나오면 1을 반환하며 종료하는 조건을 설정한다.
        return 1
    } else {      // Step 3. 이곳에 수식을 적는다. (자기 자신) + (자기 자신 -1)무한 호출
        return endNum + arithmeticSeries(endNum: endNum-1)
    }
}


print(arithmeticSeries(endNum: 1))		// 결과 : 1
print(arithmeticSeries(endNum: 2))		// 결과 : 3
print(arithmeticSeries(endNum: 10))		// 결과 : 55
print(arithmeticSeries(endNum: 100))	// 결과 : 5050
print(arithmeticSeries(endNum: 1000))	// 결과 : 500500

만약 굳이 함수 내부에 새 변수 sum을 만들고 싶다면 이렇게 하면 된다.

func arithmeticSeries(endNum:Int) -> (Int) { // Step 1. 입력 파라미터로 정수를 받아 넘긴다.
    if endNum == 1 {    // Step 2. 마지막 입력 파라미터 1이 나오면 1을 반환하며 종료하는 조건을 설정한다.
        return 1
    } else {      // Step 3. 이곳에 수식을 적는다. (자기 자신) + (자기 자신 -1)무한 호출
        var mySum = 0 + endNum
        return endNum + arithmeticSeries(endNum: mySum - 1)
    }
}

Quiz 2. 재귀함수로 A to B의 합을 구하는 등차급수 만들기.

// 내용 : A와 B를 입력받아 A부터 B까지 합을 구하는 등비급수 함수
// 파라미터 : startNum:Int, endNum:Int
// 목적 : 재귀함수를 이용해 A to B 구간의 등비급수를 구한다.

// Step 1. 입력 파라미터를 정수로 받아 넘긴다.
// Step 2. B 순서로 할꺼니 마지막 1이 나오면 종료하는 조건을 설정한다.
// Step 3. 그 외의 경우에는 리턴에 자기 자신을 -1씩 소환하며 더하는 수식을 적는다.
func arithmeticSeriesAtoB(startNum:Int, endNum:Int) -> (Int) { // Step 1. 입력 파라미터로 정수를 받아 넘긴다.
    if endNum == startNum {    // Step 2. 마지막 입력 파라미터 A to B 조건이 만족하면 startNum을 반환하며 종료하는 조건을 설정한다.
        return startNum
    } else {      // Step 3. 이곳에 수식을 적는다. (자기 자신 endNum) + (자기 자신 endNum-1)무한 호출
        return endNum + arithmeticSeriesAtoB(startNum: startNum, endNum: endNum-1)
    }
}

print(arithmeticSeriesAtoB(startNum: 100, endNum: 200))

결과 :
15150

Quiz 3. 재귀함수로 등비급수 만들기.

// 내용 : 초항과 공비, 반복횟수를 입력 받아 등비급수를 계산한다.
// 파라미터 : firstTerm(초항):Double, ratio(공비):Double, endNum:Double
// 목적 : 재귀함수를 이용해 등비급수를 구한다.

// Step 1. 입력 파라미터를 실수로 받아 넘긴다.
// Step 2. ar^(n-1) + ar^(n-2) + ... + ar + a 순서로 할꺼니 마지막에 초항이 나오면 종료하는 조건을 설정한다.
// Step 3. 그 외의 경우에는 리턴에 자기 자신을 -1항씩 소환하며 더하는 수식을 적어 넣는다.
//         ar^(n-1) + ar^(n-2)만 넣으면 재귀함수가 알아서 아래를 호출할거다. 즉, ar^(n-1) + func(-1항) 을 넣는다.
//         등비수열의 합 공식과 달리 직접 n차항을 더하는 구조라 공비 r = 1인 경우를 생각할 필요가 없다.
func geometricSeries(firstTerm:Double, ratio:Double, endNum:Double) -> (Double) { // Step 1. 입력 파라미터로 정수를 받아 넘긴다.
    if endNum == 1 {    // Step 2. 마지막 입력 파라미터 1이 나오면 1을 반환하며 종료하는 조건을 설정한다.
        return firstTerm
    } else {      // Step 3. 이곳에 수식을 적는다. ar^n + ar^(n-1) 무한 호출
        return firstTerm * pow(ratio, endNum - 1) + geometricSeries(firstTerm: firstTerm, ratio: ratio, endNum: endNum - 1)
    }
}


print(geometricSeries(firstTerm: 2, ratio: 3, endNum: 5))

결과 :
242.0

참고

인풋 파라미터를 2개 받아 아웃풋 파라미터를 2개 내보내는 Swap 함수의 경우 문법이

func swap(Int,Int) -> (Int,Int) 였다.

func swap(Int,Int) -> (Int) 로 입력할 경우 에러가 난다.

func swap(a:Int,b:Int) -> (Int,Int) {
    return (b,a)
}

하지만 등비급수의 경우

func geometricSeries(Double,Double,Double) -> (Double,Double,Double) 하면 에러가 난다.

func geometricSeries(Double,Double,Double) -> (Double) 로 입력해야한다.

처음에는 다음번 재귀함수에 firstTerm, ratio. endNum 3개의 Double 파라미터를 넘겨줘야 한다고 생각했는데 생각해보니 결국엔이 계산의 return값은 계산을 다 한 다음 숫자 하나만 내보내주는거였다. 재귀함수로 파라미터 3개 넘겨준다고 Double을 3개 적지 말자. 재귀함수는 생각하지 말고 함수 하나만 생각해보자. 실제로 return으로 내보내는 실제 값은 하나다. 나머지 값들은 하위 재귀함수가 상위 재귀함수로 던져주는 것들일 뿐이다. 튜플로 실제로 2개의 값을 반환하는 것과 혼동하지 말자.

Quiz 4. 재귀함수로 팩토리얼 만들기.

// 내용 : 입력 받은 숫자를 이용해 팩토리얼을 계산한다.
// 파라미터 : endNum:Double
// 목적 : 재귀함수를 이용해 팩토리얼을 구한다.

// Step 1. 입력 파라미터를 실수로 받아 넘긴다.
// Step 2. 100*99*...*3*2*1 순서로 할꺼니 마지막 1이 나오면 종료하는 조건을 설정한다.
// Step 3. 그 외의 경우에는 리턴에 자기 자신을 -1항씩 소환하며 곱하는 수식을 적는다.
func factorial(endNum:Double) -> (Double) { // Step 1. 입력 파라미터로 Double을 받아 넘긴다.
    if endNum == 0 {    // Step 2. 마지막 입력 파라미터 1이 나오면 1을 반환하며 종료하는 조건을 설정한다.
        return 1
    } else {      // Step 3. 이곳에 수식을 적는다. (자기 자신) * (자기 자신 -1)무한 호출
        return endNum * factorial(endNum: endNum-1)
    }
}

print("1! =", factorial(endNum: 1))
print("2! =", factorial(endNum: 2))
print("10! =", factorial(endNum: 10))
print("20! =", factorial(endNum: 20))
print("34! =", factorial(endNum: 34))        // 21! 부터는 숫자가 너무 커서 Int에는 담기지 않아 Float에 담는다.
print("100! =", factorial(endNum: 100))      // 35! 부터는 숫자가 너무 커서 Float에는 담기지 않아 Double에 담는다.
print("1000! =", factorial(endNum: 1000))    // 숫자가 너무 커서 Double로도 담을 수 없다.


결과 : 
1! = 1.0
2! = 2.0
10! = 3628800.0
20! = 2.43290200817664e+18
34! = 2.9523279903960412e+38
100! = 9.33262154439441e+157
1000! = inf

Quiz 5. 재귀함수로 피보나치 수 만들기.

// 내용 : 입력 받은 숫자를 이용해 피보나치 수를 계산한다.
// 파라미터 : Nth:Int
// 목적 : 재귀함수를 이용해 피보나치 수를 구한다.
//
// Step 1. 입력 파라미터로 정수로 받아 넘긴다.
// Step 2. Fn = F(n-1)+F(n-2), F(n-1) = F(n-2)+F(n-3), ... , F3 = F2+F1, F2 = F1+1, F1 = 1 순서로 할꺼니 마지막 1이 나오면 종료하는 조건을 설정한다.
// Step 3. 그 외의 경우에는 리턴에 (-1항) + (func(-2항))을 소환하는 수식을 적는다.
func FibonacciNumber(Nth:Int) -> (Int) { // Step 1. 입력 파라미터로 정수를 받아 넘긴다.
    if Nth == 1 || Nth == 2 {    // Step 2. F1=F2=1 이니까 초기 조건과 종료 조건을 동시에 설정한다.
        return 1
    } else {      // Step 3. 이곳에 계산 식을 적는다. Fn = F(n-1) + F(n-2)
        return FibonacciNumber(Nth: Nth - 1) + FibonacciNumber(Nth: Nth - 2)
    }
}

for i in 1...30 {
    print(FibonacciNumber(Nth: i))
}


결과 : 1~20까지는 실행 즉시 되는데 21부터 1초 22부터 2초 이런식으로 늘어나다 28부터는 급속도로 시간이 길어진다. 피보나치 수 1~30을 모두 구하는데 함수를 총 2,178,278회 반복.

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040

Quiz 6. 반복문(while)으로 피보나치 수 만들기. (재귀함수 X. 하지만 효율이 매우 좋다. 빠름!!)

// 내용 : 입력 받은 숫자를 이용해 피보나치 수를 계산한다.
// 파라미터 Nth:Int
// 목적 : 재귀함수를 사용하지 않고 엑셀 시트 행렬로 계산하듯 while함수를 통해 피보나치 수를 구한다.
//
// Step 1. 입력 파라미터를 정수로 받아 넘긴다.
// Step 2. F1=1, F2=1 초기값을 변수로 선언하고 이를 엑셀 시트 A,B열로 활용한다. FN을 선언해 이를 누적해 더할 엑셀 시트 C열로 활용한다.
// Step 3. 엑셀 시트에서 아래로 끌어 누적하는 행동을 while문을 이용해 구현한다.
func FibonacciNumberUsingWhile(Nth:Int) -> (Int){
    var F1 = 1  // F1 초항 및 Fn = F(n-1) + F(n-2) 에서 작은 값 F(n-2)를 담당.
    var F2 = 1  // F1 초항 및 Fn = F(n-1) + F(n-2) 에서 큰 값 F(n-1)를 담당.
    var FN = 1  // Fn을 담은 변수 선언
    var i = 1   // while문을 돌리기 위해 시작 변수 선언

    while i <= Nth {
        if i == 1 || i == 2 {
            i += 1
            continue    // F1, F2 까지는 i를 1씩 더해 반복문 조건만 채우고 나옴. (if문을 while 앞으로 빼고 var i = 3으로 시작해도 됨.
        } else {
            FN = F2 + F1 // F3부터 F(n-1) + F(n-2)를 수행.
            F1 = F2		// 다음번 계산할 작은 값 F(n-2)에 현재의 큰 값 F(n-1)항 값을 넣는다.
            F2 = FN	// 다음번 계산할 큰 값 F(n-1)에 현재의 작은 값 F(n-2)항 값을 넣는다.
            i += 1		// N번째 항까지 수행하기 위한 조건.
        }
    }
    return FN
}

for i in 1...30 {
    print(FibonacciNumberUsingWhile(Nth: i))
}


결과 : 재귀함수랑은 비교도 안 될 정도로 빠르다...

1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040

위의 피보나치 수를 구하는 개념은 아래 그림으로 첨부한다.

Int 범위가 너무 좁아서 100번째 피보나치 수 계산 조차 불가능해서 Double로 바꿔서 돌려봤다.

func FibonacciNumberUsingWhile(Nth:Double) -> (Double){
    var F1:Double = 1  // F1 초항 및 Fn = F(n-1) + F(n-2) 에서 작은 값 F(n-2)를 담당.
    var F2:Double = 1  // F1 초항 및 Fn = F(n-1) + F(n-2) 에서 큰 값 F(n-1)를 담당.
    var FN:Double = 1  // Fn을 담은 변수 선언
    var i:Double = 1   // while문을 돌리기 위해 시작 변수 선언

    while i <= Nth {
        if i == 1 || i == 2 {
            i += 1
            continue    // F1, F2 까지는 i를 1씩 더해 반복문 조건만 채우고 나옴. (if문을 while 앞으로 빼고 var i = 3으로 시작해도 됨.
        } else {
            FN = F2 + F1 // F3부터 F(n-1) + F(n-2)를 수행.
        	F1 = F2		// 다음번 계산할 작은 값 F(n-2)에 현재의 큰 값 F(n-1)항 값을 넣는다.
        	F2 = FN		// 다음번 계산할 큰 값 F(n-1)에 현재의 작은 값 F(n-2)항 값을 넣는다.
        	i += 1		// N번째 항까지 수행하기 위한 조건.
        }
    }
    return FN
}

for i in 1...1000 {
    print(FibonacciNumberUsingWhile(Nth: Double(i)))
}

결과 : 1~100번 피보나치를 모두 구해서 출력하는데  정도 밖에 걸리지 않았다. 1000번까지 해도 46초면 된다.

1.0
1.0
2.0
3.0
5.0
8.0
13.0
21.0
34.0
55.0
89.0
144.0
233.0
377.0
610.0
987.0
1597.0
2584.0
4181.0
6765.0
10946.0
17711.0
28657.0
46368.0
75025.0
121393.0
196418.0
317811.0
514229.0
832040.0
1346269.0
2178309.0
3524578.0
5702887.0
9227465.0
14930352.0
24157817.0
39088169.0
63245986.0
102334155.0
165580141.0
267914296.0
433494437.0
701408733.0
1134903170.0
1836311903.0
2971215073.0
4807526976.0
7778742049.0
12586269025.0
20365011074.0
32951280099.0
53316291173.0
86267571272.0
139583862445.0
225851433717.0
365435296162.0
591286729879.0
956722026041.0
1548008755920.0
2504730781961.0
4052739537881.0
6557470319842.0
10610209857723.0
17167680177565.0
27777890035288.0
44945570212853.0
72723460248141.0
117669030460994.0
190392490709135.0
308061521170129.0
498454011879264.0
806515533049393.0
1304969544928657.0
2111485077978050.0
3416454622906707.0
5527939700884757.0
8944394323791464.0
1.447233402467622e+16
2.3416728348467684e+16
3.78890623731439e+16
6.130579072161158e+16
9.919485309475549e+16
1.6050064381636707e+17
2.5969549691112256e+17
4.2019614072748966e+17
6.798916376386122e+17
1.1000877783661019e+18
1.779979416004714e+18
2.880067194370816e+18
4.66004661037553e+18
7.540113804746346e+18
1.2200160415121877e+19
1.9740274219868226e+19
3.19404346349901e+19
5.168070885485833e+19
8.362114348984843e+19
1.3530185234470676e+20
2.189229958345552e+20
3.54224848179262e+20

Xcode를 보면 1000번 모두 수행 했는데 실제 결과 프린트는 100회만 하고 더이상은 출력을 안 했다...

위에는 for문이 반복으로 수행되며 피보나치 함수에 'n번째 피보나치 수를 찾아줘'하고 요청하는거라 만약 print가 목적이라면 매번 피보나치 수를 1부터 새로 계산해야하는 매우 비효율적인 구조다.(출력 없이 피보나치 수만 찾을거면 가장 효율적인 방법이다.) 다만 어차피 출력을 할거면 매번 계산할 때마다 바로바로 출력하게 하면 처음부터 다시 계산하는 비효율성을 없앨 수 있다. 위 방법보다 더더더욱 빠른 방법을 아래 추가한다.

func FibonacciNumberUsingWhile(Nth:Double) {
    var F1:Double = 1  // F1 초항 및 Fn = F(n-1) + F(n-2) 에서 작은 값 F(n-2)를 담당.
    var F2:Double = 1  // F1 초항 및 Fn = F(n-1) + F(n-2) 에서 큰 값 F(n-1)를 담당.
    var FN:Double = 1  // Fn을 담은 변수 선언
    var i:Double = 1   // while문을 돌리기 위해 시작 변수 선언

    while i <= Nth {
        if i == 1 || i == 2 { // F1, F2 까지는 i를 1씩 더해 반복문 조건만 채우고 나옴. (if문을 while 앞으로 빼고 var i = 3으로 시작해도 됨.
            print(F1)       // F1, F2일 때는 바로 F1의 값 1을 출력.
        } else {
            FN = F2 + F1    // F3부터 F(n-1) + F(n-2)를 수행.
            print(FN)   // 다음번 계산할 작은 값 F(n-2)에 현재의 큰 값 F(n-1)항 값을 넣는다.
            F1 = F2 // 다음번 계산할 큰 값 F(n-1)에 현재의 작은 값 F(n-2)항 값을 넣는다.
            F2 = FN // N번째 항까지 수행하기 위한 조건.
        }
    i += 1
    }
}

FibonacciNumberUsingWhile(Nth: Double(1000))

결과 : 1초만에 피보나치 수 1~1000번째 까지 모두 프린트 수행...

마무리~~~~~

1. 함수가 아웃풋 파라미터가 있다면 코드를 짜기 전에 무조건 return 부터 써넣고 시작하자!

func ABC (A: Int, B: Int) -> (Int) {
	
    // 2. 로직 짜기 시작!!
    
	return	// 1. 꼭 이거 먼저 써넣고 시작하자!! 그 다음 위로 올라가 로직 짜기!!
}

2. 또한 재귀함수에서 가장 중요한 것은 탈출 조건을 가장 앞에 넣는다!!

func ABC (A: Int, B: Int) -> (Int) {
	if 	블라블라 종료조건	// 2. 그 다음에 재귀함수면 이거 적고 시작한다.

	// 3. 로직 짜기 시작!!

	return	func ABC (A: xxx, B: xxx) // 1. 아웃풋 파라미터가 있다면 이거 먼저 적고 시작한다. 
}

3. 재귀함수의 인풋 파라미터는 상수다! 인풋 파리미터가 계산을 해야하는 횟수라면 그 상수를 받아 새로운 변수를 선언하 다음번 재귀함수에 그 변수를 넘겨주거나, 리턴에 들어가는 재귀함수에 처음 들어온 인풋 파라미터에 +1 또는 -1을 해서 전달하면 된다!

왜냐하면... 함수 내부에서 '상수 = 샹수 + 1'은 불가능하지만 다음번 재귀함수에 보내는 인풋 파라미터는 '상수 + 1' 자체를 새로운 인풋 파라미터 상수로써 받아들인다.

'개발자 > Swift' 카테고리의 다른 글

Swift (스위프트) 재귀함수 - 배열의 합 구하기 & .reduce() 사용법 (0)	2020.04.08
Swift (스위프트) 2개의 정수와 연산자를 받아 계산하는 계산기 함수 만들기 (0)	2020.04.06
Swift (스위프트) 함수 예제 - BMI, Swap (0)	2020.04.04
Swift (스위프트) 함수 문법 (0)	2020.04.03
Swift (스위프트) 배열, 딕셔너리, 튜플 (0)	2020.04.01

좋은 개발자가 되자