Today What I Learned

Javascript를 배우고 있습니다. 매일 배운 것을 이해한만큼 정리해봅니다.

[Key Concepts When Coding Recursion Function]

1. Break the problem I am trying to solve down into a problem that is one step simpler
2. Assume that my function will work to solve the simpler problem — really believe it beyond any doubt
3. Ask myself: Since I know I can solve the simpler problem, how would I solve the more complex problem?

• From Learning to think with recursion from Medium by 'Daniel King'
• reference: https://medium.com/@daniel.oliver.king/getting-started-with-recursion-f89f57c5b60e

My Practices

1. Example : a recursive function that reverses a string

1. What is the One step simpler problem: I have to reverse the string from index 1 to index last.

   function reverse(string) {
   // recursive stuff should be located here
   }

   /* writing in a pseudocode
   the original probelm: to reverse string
   One step simpler problem: to reverse string[1] ~ string[last]
   the complex problem: to reverse string[0]
   */

2. What is the Base case? if the given string is one character or less, then you don't need to reverse it but instead you show the string itself. The other part belongs to the recursive case.

   function reverse(string) {
    if(string.length < 2) {
      return string;
    }
   }

3. Let's believe the one step simpler problem will be resolved by my code somehow.

   function reverse(string) {
    if(string.length < 2) {
      return string;
    }
    reverse(string.slice(1));// somehow it will work
   }

4. Now only the complex problem is left, let's focus on solving it.

function reverse(string) {
  if(string.length < 2) {
    return string;
  } else {
    return reverse(string.slice(1) + string[0]);
  }
}

2. Example : a recursive function that prints all elements in an array

1. What is the One step simpler problem: I have to print the rest of elements in the given array except the first one.

   function printArr(array) {
    // recursive stuff should be located here
   }
   /* writing in a pseudocode
   the original probelm: to print the entire array
   One step simpler problem: to print array[1] ~ array[last]
   the complex problem: to print array[0]
   */

2. What is the Base case? if the given array is one character or less and it's not an array, then you can just show the first index of it. The other part belongs to the recursive case.

   function printArr(array) {
    if(array.length < 2 && !Array.isArray(array[0])) {
      return array[0];
    }
   }

3. Let's believe the one step simpler problem will be resolved by my code somehow.

   function printArr(array) {
    if(array.length < 2 && !Array.isArray(array[0])) {
      return array[0];
    }
    let newArr = array.slice();
    newArr.shift();
    printArr(newArr);// somehow it will work
   }

4. Now only the complex problem is left, let's focus on solving it.

   function printArr(array) {
    if(array.length < 2 && !Array.isArray(array[0])) {
      return array[0];
    } else {
      let newArr = array.slice();
      newArr.shift();
      if(Array.isArray(array)) {
        return printArr(array[0]) + printArr(newArr);
      } else {
        return array[0] + printArr(newArr);
      }
    }
   }

3. Example : a recursive function that checks whether a given string is Palindrome or not

1. What is the One step simpler problem: I have to check whether the rest of characters in the given array except the first and the last character.

   function isPalindrome(str) {
    // recursive stuff should be located here
   }
   /* writing in a pseudocode
   the original probelm: to check the entire characters
   One step simpler problem: to check str[1] ~ str[last-1]
   the complex problem: to check whether str[0] is same as str[last-1]
   */

2. What is the Base case? if the given string is one or two characters, then it's true. The other part belongs to the recursive case.

   function isPalindrome(str) {
    let leng = str.length;
    if(leng <= 1) {
      return true;
    }
   }

3. Let's believe the one step simpler problem will be resolved by my code somehow.

   function isPalindrome(str) {
    let leng = str.length;
    if(leng <= 1) {
      return true;
    }
    return isPalindrom(str.slice(1, leng - 1));
    // somehow it will work
   }

4. Now only the complex problem is left, let's focus on solving it. In this case, it's divided into two cases(odd number, even number).

   function isPalindrome(str) {
    let leng = str.length;
    if(leng <= 1) {
      return true;
    } else {
      if(leng % 2 === 0) {
        return (str[0] === str[leng - 1]) && isPalindrome(str.slice(1, leng - 2));
      }
      return(str[0] === str[leng - 1]) && isPalindrome(str.slice(1, leng - 1));
    }
   }

4. Example : a recursive function that changes all elements in an array by a given callback function

1. What is the One step simpler problem: I have to change elements from second to last in the given array by the given callback function.

   function mapArr(arr, cb, result = []) {
    // recursive stuff should be located here
   }
   /* writing in a pseudocode
   the original probelm: to change the entire elements
   One step simpler problem: to change array[1] ~ array[last]
   the complex problem: to change array[0];
   */

2. What is the Base case? if the given array is empty, it returns an empty array itself.

   function mapArr(arr, cb, result = []) {
    if(!arr.length) {
      return arr;
    }
   }

3. Let's believe the one step simpler problem will be resolved by my code somehow.

   function mapArr(arr, cb, result = []) {
    if(!arr.length) {
      return arr;
    }
    let newArr = arr.slice();
    newArr.shift();
    mapArr(newArr, cb, result); // somehow it will work
   }

4. Now only the complex problem is left, let's focus on solving it.

   function mapArr(arr, cb, result=[]) {
    if(!arr.length) {
      return arr;
    }
    let newArr = arr.slice();
    newArr.shift();
    result.push(cb(arr[0]));
    mapArr(newArr, cb, result);
    return result;
   }

Summary

1. Do not think too deep to the break point that you meet the base case when coding
2. Think only two cases: 'one step simpler level' and 'complex level before the it'
3. Believe my code will resolve the 'one step simpler level'
4. Focus on the 'complex level before it' → this way, you will find base cases
5. Fill up the rest codes that connects 'one step simpler level' case to no.4.

• At first when I read this post, I got the image of his explanation but it was not easy to catch up the theme as codes. After some practices, the way I think of the recursion got clearer than before. I loved the part that he pointed out a recursion consisted of one complex case and the other simpler case. I should try more complex recursive cases later.
  연습 계속 안 하면 다 까먹게 된다... 흐미.