[자료구조] 2. Iterative, Recursive

수업을 들으면서도 매번 헤맸었던 재귀..:(

​

이번에는 실습으로 풀었던 재귀 문제 4가지를 포스팅할 것이다.

​

​

1. (재귀) Given n Boolean variables x1, ... , xn, we wish to print all possible combinations of truth values they can assume. For instance, if n = 2, there are four possibilities: <true, true>, <false, true> <true, false> and <false, false>. Write a C program to do this.

​

(해석): n이 주어졌을 때 가능한 T/F 조합을 모두 출력하여라

​

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 255

void print(int *arr, int n);
void recursive(int *arr, int index, int n);

int main(int argc, char *argv[])
{
	int n;
	int arr[MAX] = { 0 };

	printf("input n: ");
	scanf("%d", &n);

	recursive(arr, 0, n);

	return 0;
}

void print(int *arr, int n)
{
	printf("< ");
	for (int i = 0; i < n; i++) {
		if (arr[i] == 0)
		{
			printf("true ");
		}

		if (arr[i] == 1)
		{
			printf("false ");
		}
	}
	printf(">\n");
}

void recursive(int *arr, int index, int n)
{
	if (index >= n)
		return;

	arr[index] = 0;

	if (index == n - 1)
	{
		print(arr, n);
	}
	recursive(arr, index + 1, n);

	arr[index] = 1;

	if (index == n - 1)
	{
		print(arr, n);
	}
		
	recursive(arr, index + 1, n);
	
}

 

2. The factorial function n! has value 1 when n <= 1 and value n*(n-1)! when n > 1. Write both a recursive and an iterative C function to compute n!.

​

(해석): n! 계산하는 함수를 재귀, 반복 두 가지로 구현하여라

​

팩토리얼은 피보나치 수열이랑 같이 재귀 단골 문제지요오,,,

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int iteration(int num);
int recursive(int num);

int main(int argc, char *argv[])
{
	int num;

	printf("input number: ");
	scanf("%d", &num);

	printf("iteration: %d\n", iteration(num));
	printf("recursive: %d\n", recursive(num));

	return 0;
}

int iteration(int num)
{
	int result = 1;

	for (int i = 1; i <= num; i++) {
		result *= i;
	}

	return result;
}

int recursive(int num)
{
	if (num == 1)
		return 1;

	return num * recursive(num - 1);
}

 

 

3. The Fibonacci numbers are defined as: f0 = 0, f1 = 1, and fi = fi-1 + fi-2 for i > 1. Write both a recursive and an iterative C function to compute fi.

​

(해석): 피보나치 수열을 계산하는 함수를 재귀, 반복 두 가지로 구현하여라.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX 255

void iteration(int num);
int recursive(int num);

int main(int argc, char *argv[])
{
	int num;
	printf("input num: ");
	scanf("%d", &num);

	iteration(num);
	printf("recursion: %d\n", recursive(num));
}

void iteration(int num)
{
	int arr[MAX] = { 0 };
	arr[0] = 0;
	arr[1] = 1;

	for (int i = 2; i <= num; i++) {
		arr[i] = arr[i - 1] + arr[i - 2];
	}

	printf("iteration: %d\n", arr[num]);
}

int recursive(int num)
{
	if (num == 0)
		return 0;

	if (num == 1)
		return 1;

	return recursive(num - 1) + recursive(num - 2);
}