純JS實現在一個字符串b中查找另一個字符串a出現的所有位置，並且不使用字符串的方法（遞歸）
- 2019 年 10 月 3 日
- 筆記
問題：判斷字符串A在中所有出現字符串B中（長度大於1）的索引。不得使用字符串方法indexof，substring等
有小夥伴在面試遇到了這個問題，乍一看如果使用使用字符串方法indexof，substring，很簡單容易實現，但如果不使用這些方法，怎麼樣才能實現這個需求呢
// 思路: 如果不能使用字符串的相應方法，我們可以把字符串轉換成數組，使用遞歸函數不斷去比對相應的數組索引，然後把滿足條件的索引打印出來，其實很多現在前後端交互處理數據的方法，用的都是遞歸偏多，千萬別小瞧遞歸！
話不多說，我們先上解決問題的方法：
<script> // 其實很多現在前後端交互處理數據的方法，用的都是遞歸變多，千萬別小瞧遞歸 // 思路: 不能使用字符串的相應方法，我們可以把字符串轉換成數組，首先使用遞歸不斷去比對相應的數組索引 // 隨機的字符 var str1 = 'adfacddtgjacbasaclsaacdctacw'; // 條件篩選的字符 var str2 = 'basaclsa'; // 把相應的字符串轉換為數組 var arr1 = str1.split(''); var arr2 = str2.split(''); function test (arr) { // 寫一個for循環，先把需要篩選的數組arr2第一個索引拿來比對 for(var i = 0; i < arr1.length; i++){ // 如果符合，執行下一層 if(arr[0] === arr1[i]){ // 進入到這裡說明了: arr2的第一份索引的字符，和arr1的索引的字符相同相同 // 既然第一個索引相同，我們這裡就聲明一個變量num，讓變量num依據arr2的長度去遞增 var num = 0 function ccc (arr) { // 第一個索引相同，讓他們索引分別加上變量num，去比對他們索引後面的位置是否相同，如果滿足條件繼續讓num遞增 // 直到遞增變量num的值等於arr1的長度為止，這時候說明這段索引和arr1完全相同 if (arr[num] === arr1[i+num]) { if (num === arr.length-1) { console.log( '符合條件的索引是', i) } num++ // console.log(num) ccc (arr) // 如果不能滿足條件，就讓該遞歸跳出 }else { return } } ccc(arr2) } } } test(str2) </script>
其實一說起遞歸，我想每個人都不陌生。舉個從小就聽過的例子：從前有座山，山裡有座廟，廟裡有個和尚，和尚在講故事，從前有座山，山裡有座廟，廟裡有個和尚，和尚在講故事，從前有座山…
其實遞歸，就是在運行的過程中調用自己。程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型複雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重複計算，大大地減少了程序的代碼量。
實際上這張圖就很形象地表達出了遞歸。
好了，遞歸的知識差不多介紹完了。對了!簡單來說，循環是有去無回，而遞歸則是有去有回(因為存在終止條件)。
