递归函数return 深入理解

先贴一段最简单的递归函数的代码：

static int Sum(int n)
        {
            if (n <= 1)                  //#1
                return n;                //#2
            return n+Sum(n - 1);         //#3
        }

sum函数为递归求和函数，sum(3)->sum(2)->sum(1),此时return 1, 但return 1 并不是直接return到最外层，而是逐个返回到上一层的递归函数，直到第一次函数调用，return n+sum(1)->return n+sum(2).

同理，对该题
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

class Solution:
def generateParenthesis(self, n: int) -> List[str]:
      ans = []
      def backtrack(S = [], left = 0, right = 0):
          if len(S) == 2 * n:
              ans.append("".join(S))
          if left < n:
              S.append("(")
              backtrack(S, left+1, right)
              S.pop()
          if right < left:
              S.append(")")
              backtrack(S, left, right+1)
              S.pop()

backtrack()
return ans

generateParenthesis（2），函数从backtrack()开始执行， S=[], left=0,right=0-> S.append("(") backtrack(''(', 1, 0) -> S.append("((") backtrack(''((', 2, 0) -> S.append(")") backtrack(''(()'', 2, 1) -> S.append(")") backtrack(''(())'', 2, 2)->ans.append("".join(S))

此时函数返回None, 并不会直接返回到递归函数最外层，而是逐个递归到上一层所执行的函数，直到第一次执行S=[], left=0,right=0

backtrack(''(())'', 2, 1) S.pop() -> backtrack(''(()'', 2, 0) S.pop() -> backtrack(''(('', 1, 0) S.pop() -> S.append(")") backtrack(''()'', 1, 1) ->S.append("(") backtrack(''()('', 2, 1)->S.append(")") backtrack(''()()'', 2, 2) -> ans.append("".join(S))

->返回到right S.pop()->S.pop()->S.pop() 此时S=[], left=0,right=0 return ans

参考链接：

https://blog.csdn.net/weixin_40476348/article/details/98602498

https://its401.com/article/weixin_43812682/103418186

递归函数return 深入理解

相关

标签