Algorithm Review 3

오동환·2023년 3월 14일

Algorithm

목록 보기

4/23

1. Calculating Fibonacci Numbers

💡Key Concept
Inductive Reasoning could be an efficient way of understanding recursive algorithms. Based on that understanding, It would be easier to make a code for those algorithms such as calculating fibonacci numbers.

⏱️Time Complexity
A simple recursive algorithm for finding the nth Fibonacci number has a time complexity of O(2^n). This is because the algorithm recursively calculates the Fibonacci number by calling itself twice for each input value.

int calculate_nth_fibonacci(int n) {
	if (n == 1 || n ==2) {
		return 1;
	}
	else {
		return calculate_nth_fibonacci(n - 1) + calculate_nth_fibonacci(n - 2);
	}
}

2. Getting the Greatest Common Divisor

💡Key Concept
The greatest common divisor between two integers can be effectively calculated using the Euclidean algorithm and recursion".

int gcd(int m, int n) {
	if (m < n) {
		int temp;
		temp = m;
		m = n;
		n = temp;
	}
	// to use modulo operator, some constraints occur
	// 1. input should not be 0
	// 2. need to swap if m is bigger than n
	if (m % n == 0) {
		return n;
	}
	else {
		return gcd(n, m % n);
	}
}

int gcd2(int p, int q) {
    // Resolves constraints related to using modulo operator by calling gcd function
	if (q == 0) {
		return p;
	}
	else {
		return gcd(q, p % q);
	}
}

The functions below may not be very efficient, but it can be helpful for strengthening coding skills by applying the method of implementing every interation such as for and while using recursion.

#define _CRT_SECURE_NO_WARNINGS
#define SIZE 100
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int getStringLength(char* str) {
	if (*str == '\0' || *str == '\n')
		// when the string is ended
		// count the actual characters exclude '\n'
		return 0;
	else {
		return 1 + getStringLength(str + 1);
	}
}

// 1. print the first character of the obtained string
// 2. recursively call the function with the rest of the string.
void printChar(char* str) {
	if (*str == '\0') {
		return;
	}
	else {
		printf("%c", *str);
		return printChar(str + 1);
	}
}

// 1. recursively call the function with the rest of the string excluding the first character
// 2. finally print the first character of the original string.
void printCharReverse(char* str) {
	if (*str == '\0') {
		return;
	}
	else {
		printCharReverse(str + 1);
		printf("%c", *str);
	}
}

int main() {
	char* str = (char*)malloc(sizeof(char) * SIZE);

	// use fgets to get space character
	fgets(str, 100, stdin);

	printf("%d", getStringLength(str));
	printf("\n");
	printChar(str);
	printf("\n");
	printCharReverse(str);
	printf("\n");
}

// 1. match the target to the last element of the given array
// 2. do the recursive call till n gets lower than 0
int sequentialSearch(int data[], int n, int target) {
	if (n < 0)
		return -1;
	else if (data[n - 1] == target) {
		return n - 1;
	}
	else {
		return sequentialSearch(data, n - 1, target);
	}
}

int max(int a, int b) {
	if (a >= b)
		return a;
	else
		return b;
}

// recursively compare the last element with the maximum of the remaining elements.
int findMax(int data[], int n) {
	if (n == 1) {
		return data[0];
	}
	else {
		return max(data[n - 1], findMax(data, n - 1));
	}
}

Some algorithms that are effective when implemented using recursion

5. Print an Integer in Binary

void printInBinary(int n) {
	if (n < 2) {
		printf("%d", n);
	}
	else {
		printInBinary(n / 2);
		// without returning value, the modification can be printed
		printf("%d", n % 2);
	}
}

6. Find Disjoint Between Two Sorted Arrays

bool isDisjoint(int m, int A[], int n, int B[]) {
	if (m <= 0 || n <= 0) {
		return true;
	}
	else if (A[m - 1] == B[n - 1]) {
		return false;
	}
	// Since both arraies are sorted, when the last element of array A is greater than that of B,
	// all elemnts of B are less than that element.
	else if (A[m-1] > B[n-1]) {
		return isDisjoint(m - 1, A, n, B);
	}
	else {
		return isDisjoint(m, A, n - 1, B);
	}
}

Properties of Recursive Functions:

1. Every iterative function can be transformed into a recursive function.
2. Recursive functions can make complex algorithms appear simpler.
3. However, overhead such as transferring parameters and activation frames exist."

Recursive functions can be more elegant and easier to understand in some cases, but they can also be less efficient and prone to stack overflow errors if not designed properly.
Additionally, while overhead does exist in recursive functions, this should not necessarily discourage their use, as the benefits of more readable and modular code can outweigh the costs.

Tips for Implementing Recursive Functions:

It is important to clearly explain the mission of the algorithm. To achieve this, we can adopt two techniques.

1.Suggest at least one base case:
A base case is necessary to stop the recursion. Without a base case, the function will keep calling itself indefinitely, leading to a stack overflow error.
2. Use explicit parameters:
Since the recursive function calls itself, it's important to describe the mission of the function in the signature. This can help to avoid confusion and ensure that the function is implemented correctly.

🏠Take-Home-Message
I was confused about when to use return keyword in the recusrive case. The answer is you use it when the function need a return value that is from the pervious recursive function.
For instacne, finding a Fibonacci number, you use the return value because the result uses previously calculated numbers. (Even returning true or false could be essential.) On the other hand, when just reversely printing the character in a string, you don't a need return value.

7. Binary Search

int binarySearch(int data[], int left, int right, int target) {
	int mid = (left + right) / 2;
	if (left > right) {
		// Search is complete and target value was not found
		return -1;
	}
	else if (target == data[mid]) {
		// find the target
		return mid;
	}
	else if (target < data[mid]) {
		// check the left portion
		return binarySearch(data, left, mid - 1, target);
	}
	else {
		// check the right portion
		return binarySearch(data, mid + 1, right, target);
	}
}

8. Two Sum

bool twoSum(int data[], int begin, int end, int K) {
	if (begin >= end) {
		// do not allow to pick the same value for both
		return false;
	}
	else if (data[begin] + data[end ] == K) {
		return true;
	}
	else if (data[begin] + data[end] < K) {
		return twoSum(data, begin + 1, end, K);
	}
	else {
		return twoSum(data, begin, end - 1, K);
	}
}

오동환

게임 개발 공부하고 있어요

이전 포스트

알고리즘 예제들

다음 포스트

Algorithm Review 4

47개의 댓글

Hunain Khan 6

2024년 11월 17일

This unique is a fantastic put up I just spotted using show it again. Suggest whatever I wanted to ascertain optimism through forthcoming you are likely to remain for the purpose of showing this terrific put up. Best iptv

답글 달기

ali umair