递归 - 递归三要素 - 《leetcode之路》

第一要素：明确你这个函数想要干什么
对于递归，我觉得很重要的一个事就是，这个函数的功能是什么，他要完成什么样的一件事，而这个，是完全由你自己来定义的。也就是说，我们先不管函数里面的代码什么，而是要先明白，你这个函数是要用来干什么。

第二要素：寻找递归结束条件
所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，不然的话，会一直调用自己，进入无底洞。也就是说，我们需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候我们必须能根据这个参数的值，能够直接**知道函数的结果是什么。

第三要素：找出函数的等价关系式
我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。

比如：我们要求出N的阶乘。

第一步：函数目的，以及有无返回值

// 算 n 的阶乘(假设n不为0)
func f(int n) int {
}

第二步找递归结束条件

// 算 n 的阶乘(假设n不为0)
func f(int n) int {
    if n <= 2 {// 当n <= 2 时 结束递归,直接返回值
    return n 
    }
}

第三步函数等价关系

// 算 n 的阶乘(假设n不为0)
func f(int n) int {
    if n <= 2   {  // 当n <= 2 时 结束递归,直接返回值
    return n
    }
    return n * f(n-1)  // 直接返回函数等式
}

例题1

反转字符串**

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

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

// 递归 分治思路
func reverseString(s []byte)  {
    if len(s) == 0 || len(s) == 1  {
        return 
    }
    help(s,0,len(s)-1)
}
func help(s []byte,i,j int) {
    if i >= j {
        return 
    }
    s[i],s[j] = s[j],s[i]
    i++ 
    j--
    help(s,i,j)
}

//迭代  
func reverseString(s []byte)  {
  if len(s) == 0 || len(s) == 1  {
        return 
    }
    i:=0 
    j := len(s)-1
    for i < j {
        s[i],s[j] = s[j],s[i]
    }
}

例题2

杨辉三角**
https://leetcode-cn.com/leetbook/read/recursion/4mb3s/

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

//递归


// 迭代
// 杨辉三角每层的i的值都是上层决定的m[i]+m[i+1]的和
func generate(numRows int) [][]int {
    res := [][]int{}
    if numRows < 1 {
        return res 
    }
    res = append(res,[]int{1})
    for i:=1;i<numRows;i++ {
        m := []int{0}
        m = append(m,res[i-1]...)
        for j:=0;j<len(m)-1;j++ {
            m[j] = m[j] + m[j+1]
        }
        res = append(res,m)
    }
    return res 
}


//迭代另一种方式 
func generateTra(numRows int) [][]int {
    res := [][]int{}
    for i:=0;i<= numRows;i++ {
        v := make([]int,i+1)
        for j := range v {
            v[j]=1
        }
        res = append(res,v)
        for j:=1;j<i;j++ {
            res[i][j] = res[i-1][j-1] + res[i-1][j]
        }
    }
    return res
}

链表反转
**

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil  {
        return head 
    }
    node := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil 
    return node 
}

斐波拉契
**

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。

//递归，重复计算
func fib(N int) int {
    if N <= 1 {
        return N
    }
    return fib(N-1) + fib(N-2)
}


// 递归 记忆化自底向上的方法
func fib(N int) int {
    if N <= 1 {
        return N
    }
    return memoize(N)
}

func memoize(N int) int {
    cache := map[int]int{0: 0, 1: 1}

    for i := 2; i <= N; i++ {
        cache[i] = cache[i-1] + cache[i-2]
    }
    return cache[N]
}


//递归  记忆化自顶向下的方法
var cache = map[int]int{0: 0, 1: 1}

func fib(N int) int {
    if N <= 1 {
        return N
    }
    return memoize(N)
}
func memoize(N int) int {
    if _, ok := cache[N]; ok {
        return cache[N]
    }
    cache[N] = memoize(N-1) + memoize(N-2)
    return memoize(N)
}

// 自底向上进行迭代
func fib(N int) int {
    if N <= 1 {
        return N
    }
    if N == 2 {
        return 1
    }
    current := 0
    prev1 := 1
    prev2 := 1

    for i := 3; i <= N; i++ {
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    }
    return current
}


// 动态规则 记忆数组
func fib(num int) int  {
    dp := make([]int,num+1)
    dp[0] = 0 
    dp[1] = 1
    for i:=2;i<=num;i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[num]
}

// 爬楼梯
// 
func climbStairs(n int) int {
    memo := make(map[int]int)
    return climb_Stairs(0,n,memo)
}

func climb_Stairs(i,n int,memo map[int]int) int {
    if  i > n {
        return 0
    }
    if i ==n {
        return 1
    }
    if _,ok := memo[i]; ok {
        return memo[i]
    }
    memo[i] = climb_Stairs(i+1,n,memo) + climb_Stairs(i+2,n,memo)
    return memo[i]
}