菜鸟笔记
提升您的技术认知

算法详解-递归-解决复杂问题的神器

前言

递归是一种非常重要的编程技巧,它可以让我们用简洁的代码解决复杂的问题。

主要内容

主要内容: 递归是一种算法,它通过调用自身来解决问题。一个递归函数通常包括两个部分:基本情况(base case)和递归情况(recursive case)。基本情况是指函数能够直接解决的最简单问题,而递归情况则是指函数通过调用自身来解决更小规模的问题。

初级

阶乘

举个例子,我们可以使用递归来计算阶乘。阶乘表示为n!,定义为n * (n-1) * (n-2) * … * 1。我们可以将其写成一个递归函数:
C++

int factorial(int n) {
  
    if (n == 0) {
  
        return 1; // 基本情况
    } else {
  
        return n * factorial(n - 1); // 递归情况
    }
}

python

def factorial(n):
    if n==1: return 1
    else: return factorial(n-1)*n

print(factorial(4))

斐波那契数列

斐波那契数列:斐波那契数列的第n项定义为前两项之和(除了第0项和第1项分别为0和1)。我们可以使用递归来计算斐波那契数列的第n项:
C++

#include <iostream>
using namespace std;

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

int main() {
  
    int n = 10;
    cout << fib(n) << endl;
    return 0;
}

Python

def fib(n):
    if n==1 or n==2: return 1
    else: return fib(n-1)+fib(n-2)

print(fib(15))
print(fib(35))

加入哈希表记忆优化

def fib(n):
    if hash.get(n,0): return hash[n]
    res=fib(n-1)+fib(n-2)
    hash[n]=res
    return res

hash={
  1:1,2:1}

print(fib(15))
print(fib(50))

在这个例子中,fib函数接受一个参数:整数n。函数使用递归来计算斐波那契数列的第n项。
当n等于0或者1时,直接返回n作为结果。否则,返回前两项之和。

汉诺塔

汉诺塔问题:汉诺塔是一个经典的递归问题。它包括三根柱子和一些大小不等的圆盘。初始时,所有圆盘都叠在第一根柱子上,按照从大到小的顺序排列。目标是将所有圆盘移动到第三根柱子上,并保持原有顺序。每次移动只能移动一个圆盘,并且不能将大圆盘放在小圆盘上面。

我们可以使用递归来解决汉诺塔问题。假设我们要将n个圆盘从柱子A移动到柱子C,可以分为以下步骤:

将前n-1个圆盘从柱子A移动到柱子B(借助柱子C)。
将最后一个圆盘从柱子A移动到柱子C。
将前n-1个圆盘从柱子B移动到柱子C(借助柱子A)。
其中步骤1和步骤3都是规模更小的汉诺塔问题,因此可以使用递归来解决。
C++

#include <iostream>
using namespace std;

void hanoi(int n, char A, char B, char C) {
  
    if (n == 1) {
  
        cout << "Move disk 1 from " << A << " to " << C << endl;
    } else {
  
        hanoi(n - 1, A, C, B);
        cout << "Move disk " << n << " from " << A << " to " << C << endl;
        hanoi(n - 1, B, A, C);
    }
}

int main() {
  
    int n = 3; // 圆盘数量
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

Python

def hanoi(n,a,b,c):
    if n==1: print(a+"---->"+c)
    else:
        hanoi(n-1,a,c,b)
        print(a+"---->"+c)
        hanoi(n-1,b,a,c)

hanoi(2,'A','B','C')

在这个例子中,hanoi函数接受4个参数:圆盘数量n,起始柱子A,辅助柱子B和目标柱子C。函数使用递归来解决汉诺塔问题,并输出每一步的移动过程。

当圆盘数量为1时,直接将圆盘从起始柱子移动到目标柱子。否则,先将前n-1个圆盘从起始柱子移动到辅助柱子(借助目标柱子),然后将最后一个圆盘从起始柱子移动到目标柱子,最后再将前n-1个圆盘从辅助柱子移动到目标柱子(借助起始柱子)。

数组求和

给定一个整数数组,使用递归计算数组中所有元素的和。
C++

#include <iostream>
using namespace std;

int sum(int arr[], int n) {
  
    if (n == 0) {
  
        return 0;
    } else {
  
        return arr[n - 1] + sum(arr, n - 1);
    }
}

int main() {
  
    int arr[] = {
  1, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << sum(arr, n) << endl;
    return 0;
}

Python

def arr_sum(l,n):
    if n==0: return 0
    return l[n-1]+arr_sum(l,n-1)

arr = [1,2,3,4,5,10]
print(arr_sum(arr,len(arr)))

在这个例子中,sum函数接受两个参数:整数数组arr和数组长度n。函数使用递归来计算数组中所有元素的和。

当数组长度为0时,返回0作为结果。否则,返回最后一个元素加上前n-1个元素的和。

幂运算

给定两个整数x和n,使用递归计算x的n次方。
C++

#include <iostream>
using namespace std;

int power(int x, int n) {
  
    if (n == 0) {
  
        return 1;
    } else if (n % 2 == 0) {
  
        int y = power(x, n / 2);
        return y * y;
    } else {
  
        return x * power(x, n - 1);
    }
}

int main() {
  
    int x = 2;
    int n = 10;
    cout << power(x, n) << endl;
    return 0;
}

Python

def power_x_y(x,y):
    if y==0:return 1
    if y&1:return x*power_x_y(x,(y-1)>>1)**2
    return power_x_y(x,y>>1)**2
    
print(power_x_y(2,11))
print(power_x_y(2,12))

在这个例子中,power函数接受两个参数:底数x和指数n。函数使用递归来计算x的n次方。

当指数为0时,返回1作为结果。否则,根据指数的奇偶性分别处理。如果指数是偶数,则将其除以2并递归计算x的(n/2)次方,然后将结果平方;如果指数是奇数,则将其减去1并递归计算x的(n-1)次方,然后将结果乘以x。

数组翻转

给定一个整数数组,使用递归将数组翻转
C++

#include <iostream>
using namespace std;

void reverse(int arr[], int start, int end) {
  
    if (start >= end) {
  
        return;
    } else {
  
        swap(arr[start], arr[end]);
        reverse(arr, start + 1, end - 1);
    }
}

int main() {
  
    int arr[] = {
  1, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    reverse(arr, 0, n - 1);
    for (int i = 0; i < n; i++) {
  
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

Python

def swap(x, y):
    tmp=l[x]
    l[x]=l[y]
    l[y]=tmp

def reverse_list(l,start,end):
    if start>=end:return
    swap(start,end)
    reverse_list(l,start+1,end-1)

l=[1,2,3,4,5,6,7,8,9]
reverse_list(l,0,len(l)-1)
print(l)

在这个例子中,reverse函数接受三个参数:整数数组arr、起始位置start和结束位置end。函数使用递归来将数组翻转。
当起始位置大于等于结束位置时,直接返回。否则,交换两端的元素,并对剩余部分进行递归翻转。

字符串翻转

给定一个字符串,使用递归将字符串翻转。
C++

#include <iostream>
#include <string>
using namespace std;

string reverse(string str) {
  
    if (str.length() <= 1) {
  
        return str;
    } else {
  
        char first = str[0];
        string rest = str.substr(1);
        return reverse(rest) + first;
    }
}

int main() {
  
    string str = "hello";
    cout << reverse(str) << endl;
    return 0;
}

在这个例子中,reverse函数接受一个参数:字符串str。函数使用递归来将字符串翻转。

当字符串长度小于等于1时,直接返回字符串本身作为结果。否则,取出第一个字符和剩余部分,并对剩余部分进行递归翻转,然后将第一个字符添加到末尾。

中级

全排列

给定一个字符串,使用递归打印出该字符串的所有排列。
C++

#include <iostream>
#include <string>
using namespace std;

void permute(string str, int l, int r) {
  
    if (l == r) {
  
        cout << str << endl;
    } else {
  
        for (int i = l; i <= r; i++) {
  
            swap(str[l], str[i]);
            permute(str, l + 1, r);
            swap(str[l], str[i]);
        }
    }
}

int main() {
  
    string str = "ABC";
    int n = str.length();
    permute(str, 0, n - 1);
    return 0;
}

Python

#数组全排列(转化为字符串即可)
def swap(left, right):
    tmp=l[left]
    l[left] = l[right]
    l[right] = tmp
    
def all_sort(l,left, right):
    if left==right:print(l)
    else:
        for i in range(left,right+1):
            swap(left,i)
            all_sort(l,left+1,right)
            swap(left,i)

l=[1,2,3]
all_sort(l,0,len(l)-1)

在这个例子中,permute函数接受三个参数:字符串str、起始位置l和结束位置r。函数使用递归来打印出字符串的所有排列。

当起始位置等于结束位置时,直接打印字符串作为结果。否则,枚举起始位置到结束位置之间的每一个字符,并将其与起始位置的字符交换,然后对剩余部分进行递归排列。

子集

给定一个整数数组,使用递归打印出该数组的所有子集。

#include <iostream>
#include <vector>
using namespace std;

void subsets(vector<int> &arr, vector<vector<int>> &result, vector<int> &subset, int index) {
  
    result.push_back(subset);
    for (int i = index; i < arr.size(); i++) {
  
        subset.push_back(arr[i]);
        subsets(arr, result, subset, i + 1);
        subset.pop_back();
    }
}

int main() {
  
    vector<int> arr = {
  1, 2 ,3};
    vector<vector<int>> result;
    vector<int> subset;
    subsets(arr,result ,subset ,0);

   for(int i=0;i<result.size();i++){
  
       cout<<"[";
       for(int j=0;j<result[i].size();j++){
  
           cout<<result[i][j]<<" ";
       }
       cout<<"]"<<endl;
   }

   return 0;
}

这段代码是一个使用递归生成整数数组所有子集的C++程序。它定义了一个名为subsets的函数,该函数接受四个参数:整数数组arr、结果集合result、当前子集合并subset和当前索引位置index。

在主函数中,首先定义了一个整数数组arr = {1, 2 ,3},然后定义了一个结果集合和一个空的子集合并。接着调用了一次subsets(arr,result ,subset ,0)函数,以生成所有子集。

最后,程序遍历结果集合并打印出每个子集。

高级

正则表达式匹配

给定一个字符串s和一个正则表达式p,使用递归实现正则表达式匹配。

#include <iostream>
#include <string>
using namespace std;

bool isMatch(string s, string p) {
  
    if (p.empty()) {
  
        return s.empty();
    }
    bool first_match = (!s.empty() && (s[0] == p[0] || p[0] == '.'));
    if (p.length() >= 2 && p[1] == '*') {
  
        return (isMatch(s, p.substr(2)) || (first_match && isMatch(s.substr(1), p)));
    } else {
  
        return first_match && isMatch(s.substr(1), p.substr(1));
    }
}

int main() {
  
    string s = "aa";
    string p = "a*";
    cout << isMatch(s, p) << endl;
    return 0;
}

在这个例子中,isMatch函数接受两个参数:字符串s和正则表达式p。函数使用递归来实现正则表达式匹配。

当正则表达式为空时,如果字符串也为空,则返回true;否则返回false。接着判断第一个字符是否匹配。如果正则表达式的长度大于等于2且第二个字符为’*',那么可以选择忽略这两个字符或者重复第一个字符。否则,继续比较剩余部分。

N皇后问题

给定一个整数n,表示棋盘的大小为n*n,使用递归求出所有不同的n皇后摆放方案。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isValid(vector<string> &board, int row, int col) {
  
    int n = board.size();
    for (int i = 0; i < row; i++) {
  
        if (board[i][col] == 'Q') {
  
            return false;
        }
    }
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
  
        if (board[i][j] == 'Q') {
  
            return false;
        }
    }
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
  
        if (board[i][j] == 'Q') {
  
            return false;
        }
    }
   return true;
}

void backtrack(vector<vector<string>> &res, vector<string> &board, int row) {
  
   if(row==board.size()){
  
       res.push_back(board);
       return ;
   }

   int n=board[row].size();
   for(int col=0;col<n;col++){
  
       if(!isValid(board,row,col)){
  
           continue;
       }

       board[row][col]='Q';
       backtrack(res,board,row+1);
       board[row][col]='.';
   }

}

vector<vector<string>> solveNQueens(int n) {
  

   vector<vector<string>> res;
   vector<string> board(n,string(n,'.'));
   backtrack(res,board,0);
   return res;

}

int main() {
  

   int n=4;

   vector<vector<string>> result=solveNQueens(n);

   for(int k=0;k<result.size();k++){
  
       cout<<"Solution "<<k+1<<":"<<endl;
       for(int i=0;i<result[k].size();i++){
  
           cout<<result[k][i]<<endl;
       }
       cout<<endl;
   }

}

这段代码是一个使用递归解决N皇后问题的C++程序。它定义了三个函数:isValid、backtrack和solveNQueens。

其中,isValid函数用于判断在棋盘的第row行第col列放置一个皇后是否合法。它接受三个参数:棋盘board、行号row和列号col。函数通过遍历棋盘上方、右上方和左上方来判断是否有其他皇后与当前位置冲突。

backtrack函数用于回溯搜索所有可能的解。它接受三个参数:结果集合res、棋盘board和当前行号row。当row等于棋盘大小时,表示找到了一种解法,将其加入结果集合中。否则,遍历当前行的每一列,如果在该位置放置皇后合法,则继续搜索下一行。

solveNQueens函数是主要的求解函数。它接受一个整数n作为参数,表示棋盘的大小为n*n。函数首先定义了一个结果集合res和一个空棋盘board,然后调用一次backtrack(res, board, 0)函数以搜索所有可能的解。

在主函数中,首先定义了一个整数n=4,表示棋盘大小为4*4。然后调用solveNQueens(n)函数求解,并打印出所有不同的摆放方案。

总结

🦀️ ⭐
递归是一种强大而优雅的编程技巧,在解决复杂问题时非常有用。但是使用时需要注意避免无限循环和栈溢出等问题。

无限循环

避免无限循环是编写递归函数时需要注意的一个重要问题。如果递归函数没有正确地定义基本情况和递归情况,就可能出现无限循环的情况。

为了避免无限循环,我们需要确保每次递归调用都能够使问题的规模减小,最终能够达到基本情况。这样,递归函数就能够在有限的步骤内结束。

例如,在计算阶乘的例子中,我们定义了两种情况:当n等于0时,直接返回1作为结果;否则,返回n乘以(n-1)!。由于每次递归调用都会将n减小1,因此最终一定会达到基本情况n等于0。

另外,在编写递归函数时,也可以使用一些技巧来避免无限循环。例如,可以使用计数器来记录递归调用的次数,并在超过一定次数时强制结束递归。

总之,要避免无限循环,关键是要正确地定义基本情况和递归情况,并确保每次递归调用都能够使问题的规模减小。

栈溢出

栈溢出(stack overflow)是指程序在运行过程中,栈空间被耗尽的情况。这通常是由于程序中存在无限递归或者过深的递归调用导致的。

当程序运行时,每次函数调用都会在栈上分配一定的空间来存储局部变量、参数和返回地址等信息。当函数返回时,这些空间会被释放。如果函数调用层次过深,栈上分配的空间就会超过栈的容量,导致栈溢出。

栈溢出可能会导致程序崩溃或者产生不可预料的行为。因此,在编写递归函数时,应该注意避免无限递归和过深的递归调用。

如果你在解决这些问题时遇到困难,不妨多思考一下,或者寻求其他人的帮助。只要坚持不懈,相信你一定能够掌握递归这一重要技能。