목록이 정렬되어 있으면 재귀 부울 검사를 위해 python 3을 사용합니다.

Question

목록이 정렬되어 있으면 부울 검사를 수행하는 재귀 함수를 작성하려고합니다. 리스트가 소트되어있는 경우는 true를, 소트가 아닌 경우는 false를 돌려줍니다.

def isSorted(L, i=[]): 
    if L[i] > L[i + 1]: 
     return false 
    else: 
     return true 

내가 재귀에 대한 기본 케이스로 내 초기 if "L[i] > L[i + 1]:"와 수정이 있습니까 : 지금까지 내가 '기본 케이스'올바른 (즉, 내 첫 번째 '경우'문을)이있는 경우 이해하려고 노력하고 있어요?

내 '기본 케이스'가 맞다고 가정하고 목록이 비 내림차순으로 정렬되었는지 재귀 적으로 결정하는 방법을 모르겠습니다.

Answer 1

이렇게하면 시작할 수 있습니다. 다음 서명이있는 함수를 작성 : 함수 내부

function isSorted(currentIndex, collection) 

, currentIndex 컬렉션의 끝에 있는지 확인하십시오. 맞으면 true를 반환합니다.

다음으로 collection[index]과 collection[index+1]이 올바르게 정렬되어 있는지 확인하십시오.

그렇지 않은 경우 false를 반환 이러한 경우
, isSorted(currentIndex+1, collection)

이 경고 반환 : 당신이 도달하면이

Answer 2

아니, 기본 케이스가 될 것 재귀에 대한 무서운 사용이다 목록의 끝.이 경우 true를 반환합니다.

그렇지 않으면 찾고있는 두 요소가 잘못되어 있으면 false를 반환합니다.

그렇지 않으면 다음 요소에서 재귀 호출의 결과를 목록 아래로 반환하십시오.

Answer 3

@MStodd에 동의합니다. 재귀는 Python에서이 문제를 해결할 방법이 아닙니다. 매우 긴리스트의 경우, 파이썬은 스택을 오버플로 할 수 있습니다! 짧은 목록의 경우에는 괜찮을 것입니다. 선생님이이 문제를 제기하면이 방법으로해야합니다.

다음은이 문제에 대한 생각입니다. 각 재귀 호출은 다음 세 가지 중 하나를 수행해야합니다. 0) False을 반환합니다. 목록이 정렬되지 않았기 때문에 반환합니다. 1) 기본 케이스에 도달 했으므로 True을 반환하십시오. 2) 작업을 중단하고 기본 문제에 도달 할 때까지 남은 문제를 어떻게 든 작게 만듭니다. 기본 작업은 작업을 더 이상 분해 할 수없는 경우입니다.

def recursive_check(lst, i): 
    # check at the current position "i" in list 
    # if check at current position fails, return False 
    # update current position i 
    # if i is at the end of the string, and we cannot move it any more, we are done checking; return true 
    # else, if i is not at the end of the string yet, return the value returned by a recursive call to this function 

예를 들어, 여기 문자열에서 문자 '@'가 있는지 확인하는 기능이다 : 여기

는 광범위한 개요이다. 문자열에 @이 없으면 True을 반환해야합니다.

def at_check(s, i): 
    if s[i] == '@': 
     return False 
    i += 1 
    if i >= len(s): 
     return True 
    else: 
     return at_check(s, i) 

필자는 앞에서 설명한 내용과 똑같은 내용을 썼습니다. 다음은 동일한 작업을 수행하는 약간 짧은 버전이지만 정확히 같은 순서는 아닙니다.

def at_check(s, i=0): 
    if i >= len(s): 
     return True 
    if s[i] == '@': 
     return False 
    return at_check(s, i+1) 

편집 : 나는 at_check()에 인수 i=0을 넣어 통지. 즉, i의 "default"값은 0이됩니다.이 함수를 호출하는 사람은 at_check(some_string)을 호출 할 수 있으며 첫 번째 호출에 대해 0을 명시 적으로 전달하지 않을 수 있습니다. 기본 인수는 첫 번째 0 인수를 제공합니다.

i에 실제로 추가해야하는 유일한 시간은 함수를 재귀 적으로 호출 할 때입니다. 1을 더하는 부분은 중요한 "작업 중단"부분입니다. 우리가 아직 확인하지 않은 문자열의 부분은 i 뒤에있는 부분이며, 그 부분은 호출 할 때마다 작아집니다. 나는 당신이 아직 "슬라이스"에 대해 배웠는지 알지 못하지만 "조각"을 사용하여 각 호출마다 문자열을 작고 작게 만들 수 있습니다. 이런 방식으로 작동하는 버전이 있습니다. 너가 아직 썰기 알지 않으면 그것을 무시 하십시요. 이 버전에서

def at_check(s): 
    if s == '': # empty string 
     return True 
    if s[-1] == '@': # is last character '@'? 
     return False 
    return at_check(s[:-1]) # recursive call with string shortened by 1 

는 빈 문자열은 기초의 경우입니다. 빈 문자열에는 @이 포함되어 있지 않으므로 True을 반환합니다. 마지막 문자가 @ 인 경우 False을 반환 할 수 있습니다. 그렇지 않으면 마지막 문자를 잘라 버리고 함수를 재귀 적으로 호출합니다. 여기서 우리는 작업이 끝날 때까지 문자열을 문자 그대로 짧고 짧게 만들어 작업을 중단합니다. 그러나 1을 인덱스 변수에 추가하고 문자열을 통해 인덱스를 이동하는 것은 동일한 것입니다.

재귀를 사용하여 작업을 분석하고 각 재귀 호출에 대해 몇 가지 작업을 수행 할 때까지이 예제를 연구하십시오. 그런 다음 목록을 정렬할지 여부를 찾는 문제에이 아이디어를 적용하는 방법을 파악할 수 있는지 확인하십시오.

행운을 빈다.

Answer 4

여기 제가 생각한 것입니다. 기본 목록을 0으로 지정합니다. 먼저 첫 번째 항목이 마지막 항목인지 확인합니다. 그렇지 않은 경우 목록의 끝에 도달 할 때까지 각 항목을 검사해야합니다.

def isSorted(L): 
    # Base case 
    if len(L) == 1: 
     return True 

return L[0] <= L[1] and isSorted(L[1:])