> For the complete documentation index, see [llms.txt](https://ayaseeri.gitbook.io/algorithm-pattern-dart/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ayaseeri.gitbook.io/algorithm-pattern-dart/suan-fa-si-wei/recursion.md).

# 递归思维

## 介绍

将大问题转化为小问题，通过递归依次解决各个小问题

## 示例

[reverse-string](https://leetcode-cn.com/problems/reverse-string/)

> 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组  `char[]`  的形式给出。

```dart
void reverseString(List<String> s) {
  reverse(s, 0, s.length - 1);
}

void reverse(List<String> s, int start, int end) {
  if (start >= end) return;
  var temp = s[start];
  s[start] = s[end];
  s[end] = temp;
  reverse(s, ++start, --end);
}
```

[unique-binary-search-trees-ii](https://leetcode-cn.com/problems/unique-binary-search-trees-ii/)

> 给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

```dart
List<TreeNode?> generateTree(int start, int end) {
    if (start > end) {
        return [null];
    }
    List<TreeNode> allTrees = [];
    // 枚举可行根节点
    for (int i = start; i <= end; i++) {
        // 获得所有可行的左子树集合
        List<TreeNode?> leftTrees = generateTree(start, i - 1);

        // 获得所有可行的右子树集合
        List<TreeNode?> rightTrees = generateTree(i + 1, end);

        // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
        for (var left in leftTrees) {
            for (var right in  rightTrees) {
                TreeNode currTree =  TreeNode();
                currTree.val = i;
                currTree.left = left;
                currTree.right = right;
                allTrees.add(currTree);
            }
        }
    }
    return allTrees;
}

List<TreeNode?> generateTrees(int n) {
    if (n == 0) {
        return [];
    }
    return generateTree(1, n);
}
```

## 递归+备忘录

[fibonacci-number](https://leetcode-cn.com/problems/fibonacci-number/)

> 斐波那契数，通常用  F(n) 表示，形成的序列称为斐波那契数列。该数列由  0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0,   F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定  N，计算  F(N)。

```dart
  Map<int,int> mapOne = {} ;
  int fib(n){
    if(n < 2) return n;
    if(mapOne.containsKey(n)){
      return mapOne[n] ?? 0;
    } else {
      mapOne[n] = fib(n-1) + fib(n-2);
      return mapOne[n] ?? 0;
    }
  }
```

## 练习

* [ ] [reverse-string](https://leetcode-cn.com/problems/reverse-string/)
* [ ] [swap-nodes-in-pairs](https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
* [ ] [unique-binary-search-trees-ii](https://leetcode-cn.com/problems/unique-binary-search-trees-ii/)
* [ ] [fibonacci-number](https://leetcode-cn.com/problems/fibonacci-number/)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://ayaseeri.gitbook.io/algorithm-pattern-dart/suan-fa-si-wei/recursion.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.