7가지 알고리즘 챌린지로 재귀 연습하기
이것은 특히 기술 인터뷰 설정에서 일반적인 시나리오인 것처럼 보이기 때문에, 특히 기술 인터뷰 설정에서 일반적인 시나리오인 것처럼 반복적인 뇌 근육을 유연하게 만드는 데 도움이 되는 고전적인 알고리즘 문제 목록을 작성하고 있습니다. .....🙃
도전 목록
1. 문자열 반전
/* Instruction:
Given a string, write a recursive function to return the reversed string. */
// Example:
reverseString('covid')
// => 'divoc'
This one seems to be the first challenge every code newbie encounters. If you haven't solved this problem with recursion yet, I encourage you to try it out before reading further.
Here's my solution, which can be refactored via a ternary operator:
function reverseString(str) {
// base case: when there's no string to reverse
if (str === '') {
return ''
} else {
// recursive case:
// (1) grab the last character of current string,
// (2) call the same function
// (3) pass in a substring that does NOT include the last character
// (4) return (1) + (2)
return str[str.length - 1] + reverseString(str.substring(0, str.length - 1))
}
}
2. 숫자 더하기
/* Instruction:
Given an array and an index, write a recursive function to add up the elements of an array. */
// Examples:
addingUpTo([1, 4, 5, 3], 2)
// => 10
// => adding the number all the way up to index 2 (1 + 4 + 5)
addingUpTo([4, 3, 1, 5], 1)
// => 7
// => adding the number all the way up to index 1 (4 + 3)
Because we are returning the sum of multiple numbers, I immediately think of declaring a variable sum .
Also, since we are given an index, I decided to initiate sum as the element at that index and add the numbers backward.
The base case would be when we reach the end of the operation, which in this case is index 0, as we are adding backward.
function addingUpTo(arr, idx) {
// initiate sum at arr[idx]
let sum = arr[idx]
// base case: idx === 0
if (idx === 0) {
return sum
}
// adding backward
return sum + addingUpTo(arr, idx - 1)
}
3. 가장 큰 정수 찾기
/* Instruction:
Given an array, write a recursive function to find the largest integer in an array. */
// Examples:
maxOf([1, 4, 5, 3])
// => 5
maxOf([3, 1, 6, 8, 2, 4, 5])
// => 8
This is a comparison problem. So naturally, the base case would be when we cannot make a comparison, i.e. when there's only one element left in the array.
Now, how might we keep comparing and reducing the elements in the array in order to reach the base case?
The splice method in JavaScript came to my rescue.
Thanks to the mutability of splice method, I can compare the first two elements in the array, remove the smaller one, and recursively call the function with an updated array, like so:
function maxOf(arr) {
// base case: only one element left in arr
if (arr.length === 1) {
return arr[0]
}
// compare first two elements and remove smaller one
if (arr[1] > arr[0]) {
arr.splice(0, 1) // remove arr[0]
} else {
arr.splice(1, 1) // remove arr[1]
}
return maxOf(arr)
}
4. 특정 요소 찾기
/* Instruction:
Given an array and a number, write a recursive function to see if the array includes the given element. */
// Examples:
includesNumber([1, 4, 5, 3], 5)
// => true
includesNumber([3, 1, 6, 8, 2, 4, 5], 9)
// => false
Similar to the maxOf() function, we need to compare the elements in the array against the given number.
We can immediately return true once we found a match; if not, we can call the function recursively and pass in the array minus the element we just compared with until we reach the base case.
The base case I've established here is when there's no element left in the array, in which case we return false , as none of the elements inside the array matches the given number.
function includesNumber(arr, num) {
// base case: no element is left to compare
if (arr.length === 0) {
return false
}
if (arr[0] === num) {
return true
} else {
let newArr = arr.slice(1)
return includesNumber(newArr, num)
}
}
In hindsight, I should've used splice instead of slice method to remove the current element. Using slice will trigger a new copy of the array in each recursive function call, which might slow down the operation if given a larget dataset.
5. 회문
/* Instruction:
Given a string, write a recursive function to see if a word is a palindrome. */
// Examples:
isPalindrome('madam')
// => true
isPalindrome('covid')
// => false
A palindrome is a word or phrase that reads the same if you reverse the order of every opposing character.
I approached this problem with a mirror in mind: compare the first and last character of the string in each recursive function until we reach the middle point, which becomes our base case.
In the recursive case, we should immediately return false if the current character does not equate to the opposing character, as this does not satisfy the composition of a palindrome.
function isPalindrome(str) {
// base case: reaching midpoint, or empty str
if (str.length <= 1) {
return true
}
if (str[0] !== str[str.length - 1]) {
return false
} else {
return isPalindrome(str.substring(1, str.length - 1))
}
}
6. 순열
/* Instruction:
Given a string, write a recursive function to print out an array of all possible permutations of the string. */
// Examples:
permutations('abc')
// => ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
permutations('aabc')
// => ["aabc", "aacb", "abac", "abca", "acab", "acba", "baac", "baca", "bcaa", "caab", "caba", "cbaa"]
A permutation is the rearrangement of a set of items. Now, we need at least 2 elements to accomplish permutation. If the string only has one character or less, there's nothing to rearrange, so that would be our base case.
The recursive case is a tricky one for me. Unlike the previous challenges, this time we need several layers of operations to achieve desired results:
function permutations(str) {
let arr = []
// base case: less than 2 characters in the string
if (str.length < 2) {
arr.push(str)
return arr
}
for (let i = 0; i < str.length; i++) {
let currentChar = str[i]
let remainingStr = str.slice(0, i) + str.slice(i + 1, str.length)
let remainingPermutation = permutations(remainingStr) // save the result of the recursive function
// if we find a repeating character, don't add it to the arr
if (str.indexOf(currentChar) !== i) {
continue
}
// concat currentChar with each substring and push to the arr
remainingPermutation.forEach(subString => arr.push(currentChar + subString))
}
return arr
}
As commented in the code snippet, in the recursive case, not only do we need to factor in the case where there are repeating characters in the given string, we also have to concatenate the current character with each permutation of the result of the recursive function.
If you still find it confusing, I highly recommend this detailed walk-through , 이 문제에 대한 재귀 솔루션을 이해하는 데 도움이 되었습니다.7. 피보나치
/* Instruction:
Given a number, write a recursive function to
print out the n-th entry in the fibonacci series.
Fibonacci series is a sequence,
where each number is the sum of the preceding two:
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34] */
// Example:
fib(3)
// => 2
fib(6)
// => 8
I heard that it is not common to come up with the recursive solution without looking it up, so here's the "textbook" version, which, according to some experienced developers, is a formula worth memorizing:
function fib(n) {
if (n < 2) {
return n
}
return fib(n - 1) + fib(n - 2)
}
The runtime complexity of this recursive approach is exponential ( O(2^n) ), so it is not as performant as the plain-old iterative approach ( O(n) ).
You can utilize the memoization technique to optimize the recursion, which is beyond the scope of this article.
마지막 생각들
우리 모두는 재귀를 사용하여 문제를 해결하는 다른 접근 방식을 가지고 있습니다. 내 자신의 전략을 개발하는 데 몇 가지 연습이 필요했습니다.
현재로서는 여러 리소스에서 제안한 대로 기본 사례를 파악하는 것으로 시작하는 경향이 있습니다. 그런 다음 일반적으로 하위 작업을 생성하고 하위 작업의 결과를 결합하는 재귀적 사례를 살펴보겠습니다.
당신은 어때요? 재귀적으로 생각하도록 두뇌를 훈련시키는 방법은 무엇입니까? 댓글로 알려주세요!
Reference
이 문제에 관하여(7가지 알고리즘 챌린지로 재귀 연습하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/liaowow/practicing-recursion-with-7-algorithm-challenges-41ik텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
