将迭代转换为递归 [英] Turning iteration into recursion

问题描述

我想检查输入的字符串用户是否具有平衡金额（和）'s

I want to check if the string user entered has a balanced amount of ( and )'s

ex。 （）（不均衡
（（））是平衡的

ex. ()( is not balanced (()) is balanced

def check(string):

        counter=0
        string=string.replace(" ","")

        if string[0] is "(":

           for x in string:
                if x is "(":
                        counter=counter+1
                elif x is ")":
                        counter=counter-1

           if counter1 is 0:
                print("Balanced")
           else:
                print("Unbalanced")
        else:
                print ("Unbalanced")

所以这样可行，但是如何通过递归来解决这个问题呢？我试着想一想，每当我递归调用它时，我可以使变量减少，一旦它为0，就停止。

so this works, but how do I solve this problem with recursion? I am trying to think how I can make a variable decrease each time i call it recursively and once it's 0, stop.s

推荐答案

算法的直接等效转换如下所示：

A direct, equivalent conversion of the algorithm would look like this:

def check(string, counter=0):
  if not string:
    return "Balanced" if counter == 0 else "Unbalanced"
  elif counter < 0:
    return "Unbalanced"
  elif string[0] == "(":
    return check(string[1:], counter+1)
  elif string[0] == ")":
    return check(string[1:], counter-1)
  else:
    return check(string[1:], counter)

像这样使用：

check("(())")
=> "Balanced"

check(")(")
=> "Unbalanced"

请注意，上述算法考虑了右括号出现之前的情况相应的左括号，这要归功于 elif计数器< 0 条件 - 因此解决了原始代码中存在的问题。

Notice that the above algorithm takes into account cases where the closing parenthesis appears before the corresponding opening parenthesis, thanks to the elif counter < 0 condition - hence fixing a problem that was present in the original code.

这篇关于将迭代转换为递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！