본문 바로가기
컴퓨터 기초/자료구조

2.재귀

by 인생여희 2020. 8. 31.

 

 

재귀함수의 기본적인 이해

 

javascript 로 구현한 재귀함수 예제

<!DOCTYPE html>
<html>
<body>
<h2>-</h2>
</body>
<script>
//while 문을 이용한 팩토리얼 함수
var factorial = function(n) {
var result = 1;
var tempNum = 0;
var total = n;
if(total == 0 ){
return 1;
}else{
while(true){
if(tempNum >= total){
break;
}
result *= (tempNum + 1);
tempNum++;
}
}
return result;
};
console.log("5! = " + 5*4*3*2*1);
console.log("5! = " + factorial(5));
console.log("0! = 1");
console.log("0! = " + factorial(0));
console.log("-----");
//for 문을 이용한 팩토리얼 함수
var factorial2 = function(n) {
var result = 1;
var total = n;
//0 팩토리얼이면 1을 리턴
if(total == 0 ){
return 1;
}else{
for(var i = 0 ; i < total; i++){
result *= (i + 1);
}
}
return result;
};
console.log("6! = " + 6*5*4*3*2*1);
console.log("6! = " + factorial2(6));
console.log("0! = 1");
console.log("0! = " + factorial2(0));
</script>
</html>
<!--
index.html:37 5! = 120
index.html:38 5! = 120
index.html:39 0! = 1
index.html:40 0! = 1
index.html:44 -----
index.html:68 6! = 720
index.html:69 6! = 720
index.html:70 0! = 1
index.html:71 0! = 1
-->
view raw a.html hosted with ❤ by GitHub

 

재귀함수의 간단한 예제

//재귀 함수 예제
#include <stdio.h>
static void MyRecursive(int num){
if (num < 0) {
return;
}
printf("MyRecursive num : %d \n" , num);
MyRecursive(num -1);
}
int main(int argc, char* argv[]){
MyRecursive(4);
return 0;
}
/*
MyRecursive num : 4
MyRecursive num : 3
MyRecursive num : 2
MyRecursive num : 1
MyRecursive num : 0
*/
view raw aaa.c hosted with ❤ by GitHub

 

팩토리얼의 이해

 

재귀함수를 이용한 팩토리얼 예제

#include <stdio.h>
// 재귀 함수를 이용한 팩토리얼
static int MyRecursive(int num){
int result = 0;
if (num == 0) {
return 1;
}else{
result = num * MyRecursive(num -1);
return result;
}
}
int main(int argc, char* argv[]){
printf("1! = %d \n", MyRecursive(1));
printf("2! = %d \n", MyRecursive(2));
printf("3! = %d \n", MyRecursive(3));
printf("4! = %d \n", MyRecursive(4));
printf("9! = %d \n", MyRecursive(9));
return 0;
}
/*
1! = 1
2! = 2
3! = 6
4! = 24
9! = 362880
*/
view raw ffff.c hosted with ❤ by GitHub

 

피보나치 수열 함수의 이해

 

피보나치 수열 함수의 흐름

재귀함수를 이용한 피보나치 수열

#include <stdio.h>
//피보나치 수열
//0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
static int MyFibo(int num){
//첫번째 수는 0
if (num == 1) {
return 0;
//두번째 수는 1
}else if (num == 2) {
return 1;
}else{
return MyFibo(num-1) + MyFibo(num-2);
}
}
int main(int argc, char* argv[]){
printf("3번째 수 %d \n", MyFibo(3));
printf("5번째 수 %d \n", MyFibo(5));
printf("7번째 수 %d \n", MyFibo(7));
return 0;
}
/*
출력:
3번째 수 1
5번째 수 3
7번째 수 8
*/
view raw fibo.c hosted with ❤ by GitHub

 

이진 탐색 알고리즘의 재귀구현의 이해

 

이진 탐색 알고리즘의 재귀구현

//이진 탐색 - 배열의 내용이 순서대로 정렬이 되어 있어야 함.
//이진 탐색
#include <stdio.h>
/*
이진 탐색 알고리즘의 재귀적 구현
수식적으로 표현하기는 부적절하지만 이 알고리즘의 논리 자체는 재귀적이기 때문에 충분히 가능하다.
대상을 찾을때 까지 동일한 패턴을 반복하는 것이므로 재귀적인 성격을 지녔다고 볼 수 있다.
1, 탐색 범위의 중앙에 목표 값이 저장되었는지 확인
2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색
*/
/*
배열, 배열길이, 찾을 숫자
찾는 숫자가 배열에 있으면 index 반환
없으면 -1 반환
*/
int BSearch(int ar[], int first , int last, int target){
//중간값
int mid;
if (first > last) return -1;
mid = (first + last) / 2;
//배열에 target 값이 존재할때
if (ar[mid] == target){
return mid;
}
//target 값이 중간인덱스 값보다 클때
if (ar[mid] < target) {
first = mid + 1;
return BSearch(ar , first , last , target);
//target 값이 중간인덱스 값보다 작을때
}else if(ar[mid] > target){
last = mid -1;
return BSearch(ar , first , last , target);
}
return -1; //찾지 못했을때
}
int main(int argc, const char * argv[]) {
//배열
int arr[] = {1,2,3,4,5,6,7,8};
//배열 길이
int leng = sizeof(arr)/sizeof(int);
//결과
int result = BSearch(arr ,0 , leng-1 , 8);
if (result == -1) {
printf("해당 값이 없습니다.\n");
}else{
printf("배열의 %d 번째에 해당 값이 존재합니다.\n" , result);
}
//배열의 7 번째에 해당 값이 존재합니다.
return 0;
}
view raw binarysearch.c hosted with ❤ by GitHub

 

 

 

참고: 윤성우의 열혈 자료구조

저작자표시

'컴퓨터 기초 > 자료구조' 카테고리의 다른 글

스택  (0) 2021.01.24
큐  (0) 2021.01.24
4.연결리스트 - 연결리스트  (0) 2020.09.02
3.연결리스트 - 배열  (0) 2020.09.02
1.자료구조와 알고리즘의 이해  (0) 2020.08.31

관련글

티스토리툴바