Sequences

시퀀스는 정렬된 값들의 컬렉션이다. 시퀀스는 컴퓨터 과학에서 강력하고 근본적인 추상화 개념이다. 시퀀스는 특정 내장 타입이나 추상 데이터 표현의 인스턴스가 아니라, 여러 서로 다른 데이터 타입들이 공유하는 행동들의 컬렉션이다. 즉, 시퀀스에는 많은 종류가 있지만, 그것들은 모두 공통된 행동을 공유한다. 특히 다음과 같은 특성을 가진다.

• 길이 : 시퀀스는 유한한 길이를 가진다. 빈 시퀀스의 길이는 0이다.
• 요소 선택 : 시퀀스는 자신의 길이보다 작고 0부터 시작하는 임의의 비음수 정수 인덱스에 대응하는 요소를 가진다. 첫번째 요소의 인덱스는 0이다.

파이썬은 시퀀스에 해당하는 여러 원시 데이터 유형을 포함하고 있으며, 그중 가장 중요한 것은 list 이다.

Lists

리스트 값은 임의의 길이를 가질 수 있는 시퀀스이다. 리스트는 방대한 내장 행동 집합과 더불어, 그러한 행동들을 표현하기 위한 특정 구문을 가지고 있다. 우리는 이미 리스트 인스턴스로 평가되는 리스트 리터럴과, 리스트 내부의 값으로 평가되는 요소 선택 표현식을 살펴보았다. 내장 함수인 len은 시퀀스의 길이를 반환한다. 아래 예시에서 digits는 4개의 요소를 가진 리스트이다. 인덱스 3에 있는 요소는 8이다.

게다가 리스트들은 서로 더해질 수 있으며, 정수와 곱해질 수도 있다. 시퀀스에서 덧셈과 곱셈은 각 요소를 더하거나 곱하는 것이 아니라, 시퀀스 그 자체를 결합하고 복제한다. 즉, operator 모듈의 add 함수는 더해진 인자들이 이어 붙여진 리스트를 생성한다. opertor 모듈의 mul 함수는 리스트와 정수 k를 받아 원래 리스트가 k 번 반복되어 구성된 리스트를 반환한다.

다른 리스트를 포함하여 그 어떤 값도 리스트의 요소로 포함될 수 있다. 리스트를 포함하고 있는 리스트에서 깊숙이 중첩된 요소를 선택하기 위해 요소 선택 연산을 여러번 적용할 수도 있다.

Sequence Iteration

많은 경우, 우리는 시퀀스의 요소들을 하나씩 순회하며 각 요소에 대해 차례대로 어떤 계산을 수행하고 싶어 한다. 이 패턴은 매우 흔하기 때문에 파이썬은 시퀀스 데이터를 처리하기 위한 추가적인 제어문인 for을 제공한다.

어떤 값이 시퀀스에 몇 번 등장하는지 세는 문제를 생각해보자. 우리는 while 루프룰 사용하여 이 횟수를 계산하는 함수를 구현할 수 있다.

파이썬의 for문은 index라는 이름을 따로 도입하지 않고 요소의 값들을 직접 순회함으로써 이 함수 본문을 단순화 할 수 있다.

for문은 다음과 같은 형태의 단일 절로 구성된다.

for문은 다음과 같은 절차로 실행된다.

1. 헤더의 <표현식>을 평가한다. 이 표현식은 반드시 반복 가능한(iterable) 값이어야 한다.
2. 그 반복 가능한 값에 들어있는 각 요소 값에 대해 차례대로 다음을 수행한다.

• 현재 프레임에서 <이름>을 해당 요소 값에 바인딩한다.
• <코드블럭>을 실행한다.

이 실행 절차는 iterable 값이라는 개념을 참조한다. 리스트는 시퀀스의 한 종류이며, 시퀀스는 반복 가능한 값이다. 시퀀스의 요소들 그것이 나열된 순서대로 처리된다. 파이썬에는 다른 반복 가능한 타입들도 존재하지만 지금은 시퀀스에 집중해보자.

이 평가 절차의 중요한 결과 중 하나는, for 문이 모두 실행된 후 헤더의 <이름>이 시퀀스의 마지막 요소에 바인딩된 상태로 남는다는 점이다. for 루프는 이처럼 문장에 의해 환경이 업데이트 될 수 있는 방법을 제공한다.

Sequence unpacking 프로그램에서 흔히 볼 수 있는 패턴 중 하나는 고정된 길이를 가진 시퀀스들이 요소로 들어있는 시퀀스를 다루는 것이다. for문은 헤더에 여러 개의 이름을 포함하여, 각 요소 시퀀스를 각각의 성분으로 언패킹 할 수 있다. 예를 들어, 2개의 요소를 가진 리스트들을 원소로 하는 리스트가 있다고 해보자.

그리고 이 쌍들 중에서 첫 번째 요소와 두 번째 요소가 같은 쌍이 몇개인지 찾고 싶다고 가정해 보자.

헤더에 두 개의 이름을 가진 다음 for 문은 각 쌍의 첫번째 요소와 두 번째 요소를 각각 x와 y라는 이름에 차례대로 바인딩한다.

고정된 길이의 시퀀스에 있는 여러 값을, 여러 이름에 동시에 바인딩하는 이 패턴을 시퀀스 언패킹이라고 부른다. 이는 여러 이름에 여러 값을 한번에 바인딩하는 할당문에서 볼 수 있는 패턴과 동일하다.

Ranges range는 파이썬의 또 다른 내장 시퀀스 타입으로, 정수의 범위를 나타낸다. 레인지는 2개의 정수 인자를 받는 range 함수로 생성된다. 첫번째 인자는 시작하는 숫자이고, 두 번째 인자는 원하는 범위의 마지막 숫자보다 1 큰 숫자이다.

range 객체에 리스트 생성자를 호출하면 레인지와 동일한 요소를 가진 리스트로 평가되므로, 요소들을 쉽게 확인할 수 있다.

인자가 하나만 주어지면, 이는 0부터 시작하는 범위의 마지막 값보다 1큰 숫자로 해석된다.

레인지는 for 헤더의 표현식으로 자주 등장하여 코드블럭이 실행되어야 하는 횟수를 지정하는 데 사용된다. 흔히 사용하는 관례로 for 헤더의 이름이 코드블럭 안에서 사용되지 않을 때는 이름 자리에 단일 밑줄 문자를 사용한다.

인터프리터의 입장에서는 이 밑줄 문자도 환경에 존재하는 평범한 이름 중 하나일 뿐이지만, 프로그래머들 사이에서는 이 이름이 앞으로 어떤 표현식에도 등장하지 않을 것임을 나타내는 관례적인 의미를 가진다.

Sequence Processing

시퀀스는 매우 흔한 형태의 복합 데이터이기 때문에, 전체 프로그램이 종종 이 하나의 추상화를 중심으로 구성되기도 한다. 시퀀스를 입력과 출력으로 모두 가지는 모듈화된 구성 요소들은 서로 혼합되고 매치되어 데이터 처리를 수행할 수 있다. 각각의 기능이 단순하고 집중된 시퀀스 처리 연산들을 파이프라인처럼 사슬로 엮어줌으로써 복잡한 구성 요소를 정의할 수 있다.

List Comprehensions 많은 시퀀스 처리 연산은 시퀀스의 각 요소에 대해 고정된 표현식을 평가하고, 그 결과 값들을 결과 시퀀스에 수집하는 방식으로 표현될 수 있다. 파이썬에서 list comprehension은 이러한 계산을 수행하는 표현식이다.

위 코드의 for 키워드는 for 문의 일부가 아니라, 대괄호 안에 포함되어 있기 때문에 comprehension의 일부이다. 하위 표현식인 x+1은 x가 odds의 각 요소에 차례대로 바인딩디면서 평가되며, 그 결과 값들이 하나의 리스트로 수집된다.

또 다른 흔한 시퀀스 처리 연산은 어떤 조건을 만족하는 값들의 부분집합을 선택하는 것이다. comprehension은 이러한 패턴도 표현할 수 있는데, 예를 들어 odds의 요소 중 25를 나누어떨어지게 하는 모든 요소를 선택할 수 있다.

list comprehension의 일반적이 형태는 아래와 같다.

comprehension을 평가하기 위해, 파이썬은 먼저 iterable 값을 반환하는 <시퀀스 표현식>을 평가한다. 그런 다음 각 요소에 대해 차례대로 요소 값을 <이름>에 바인딩하고, <필터 표현식>을 평가하여 그것이 참인 값을 내놓으면 <맵 표현식>을 평가한다. 마지막으로 <맾 표현식>의 값들이 리스트로 수집된다.

Aggregation 시퀀스 처리의 세 번째 공통 패턴은 시퀀스의 모든 값들을 하나의 값으로 집계 하는 것이다. 내장 함수인 sum,min,max는 모두 집계 함수의 예시이다.

각 요소에 대해 표현식을 평가하는 패턴(Map), 요소의 부분집합을 선택하는 패턴(Filter), 그리고 요소들을 집계하는 패턴(Reduce)를 결합함으로써, 우리는 시퀀스 처리 접근 방식을 사용하여 문제들을 해결할 수 있다.

완전수 (perfect number)는 약수들의 합이 자기 자신과 같아지는 양의 정수이다. n의 약수란 n보다 작으면서 n을 나누어떨어지게 하는 양의 정수이다. n의 약수들을 나열하는 것은 comprehension으로 표현할 수 있다.

divisors를 사용하면 또 다른 comprehension을 통해 1부터 1000사이의 모든 완전수를 계산할 수 있다.

우리는 변의 길이가 정수인 직사각형의 면적이 주어졌을 때, 이 직사각형이 가질 수 있는 최소 둘레를 찾는 다른 문제를 해결하기 위해 divisors 정의를 재사용할 수 있다. 직사각형의 면적은 높이 * 너비이다. 따라서 면적과 높이가 주어지면 너비를 계산할 수 있다. 변의 길이가 정수임을 보장하기 위해, 너비와 높이가 모두 면적을 나누어떨어지게 한다고 단언할 수 있다.

직사각형의 둘레는 모든 변의 길이의 합이다.

변의 길이가 정수인 직사각형의 높이는 반드시 면적의 약수여야 한다. 우리는 모든 가능한 높이를 고려함으로써 최소 둘레를 계산할 수 있다.

고차 함수 시퀀스 처리에서 우리가 관찰한 공통 패턴들은 고차함수를 사용해서도 표현될 수 있다. 첫째, 시퀀스의 각 요소에 대해 표현식을 평가하는 것은 각 요소에 함수를 적용하는 것으로 표현할 수 있다.

어떤 표현식이 참인 요소들만 선택하는 것 역시 각 요소에 함수를 적용하는 것으로 표현할 수 있다.

마지막으로 많은 형태의 집계는 두 개의 인자를 받는 함수를 지금까지 축소된 값과 각 요소에 차례대로 반복해서 적용하는 방식으로 표현될 수 있다.

예를 들어 reduce를 사용하면 시퀀스의 모든 요소를 서로 곱할 수 있다. reduce_fn으로 mul을 사용하고 초기 값으로 1을 사용하면, reduce를 통해 숫자 시컨스의 곱을 구할 수 있다.

이 고차 함수들을 사용해서도 완전수를 찾을 수 있다

관례적인 이름들 cs 커뮤니티에서 apply_to_all에 대한 일반적인 이름은 map이고 keep_if에 대한 일반적인 이름은 filter이다. 파이썬에서 내장 함수인 map과 filter는 리스트를 반환하지 않는 방식으로 이 함수들을 일반화한 것이다. 위의 정의들은 내장 map과 filter 호출의 결과에 list()를 적용하는 것과 동일하다.

reduce 함수는 파이썬 표준 라이브러리의 functools 모듈에 내장되어 있다.

파이썬 프로그램에서는 고차 함수를 직접 쓰는 것보다 comprehension을 대괄호와 함께 직접 사용하는 것이 더 일반적이지만, 시퀀스를 처리하는 이 두 가지 접근 방식 모두 널리 사용된다.

Seuquence Abstrraction

우리는 시퀀스 추상화를 만족하는 두 가지 원시 데이터 유형인 list와 range를 도입했다. 두 타입 모두 이 장을 시작할 때 언급했던 조건인 길이와 요소 선택을 만족한다. 파이썬은 시퀀스 추상화를 확장하는 두 가지 시퀀스 타입의 행동을 추가로 포함한다.

Membership 어떤 값이 시퀀스에 포함되어 있는지 테스트 할 수 있다. 파이썬에는 요소가 시퀀스에 나타나는지 여부에 따라 True False로 평가되는 두 가지 연산자 in과 not in이 있다.

Slicing 시퀀스는 그 내부에 더 작은 시퀀스를 포함할 수 있다. 시퀀스의 슬라이스는 정수 쌍으로 지정되는 원래 시퀀스의 임의의 연속적인 구간이다. range 생성자와 마찬가지로, 첫 번째 정수는 슬라이스의 시작 인덱스를 나타내고 두 번째 정수는 마지막 인덱스보다 1 큰 숫자를 나타낸다.

파이썬에서 시퀀스 슬라이싱은 대괄호를 사용하여 요소 선택과 유사하게 표현된다. 콜론이 시작 인덱스와 끝 인덱스를 구분한다. 생략된 경계는 극단값으로 간주된다. 즉, 시작 인덱스가 생략되면 0으로, 끝 인덱스가 생략되면 시퀀스의 실이로 간주된다.

파이썬 시퀀스 추상화의 이러한 추가적인 행동들을 열개해보는 것은, 일반적으로 무엇이 유용한 데이터 추상화를 구성하는지 되돌아볼 기회를 제공한다. 추상화의 풍부함은 상반된 결과를 낳는다. 추상화를 사용하는 사람의 입장에서는 추가적인 행동들이 도움이 될 수 있다. 반면에, 새로운 데이터 타입으로 이처럼 풍부한 추상화의 요구사항을 모두 만족시키는 것은 까다로운 도전이 될 수 있다. 풍부한 추상화가 갖는 또 다른 부정적인 결과는 사용자가 이를 배우는 데 더 오랜 시간이 걸린다는 점이다.

시퀀스가 이처럼 풍부한 추상화를 갖게 된 이유는, 시퀀스가 컴퓨터 계산에서 매우 도처에 존재하기 때문에 몇 가지 복잡한 행동을 배울 만한 가치가 충분하기 때문이다. 일반적으로 대부분의 사용자 정의 추상화는 가능한 한 단순하게 유지되어야 한다

Strings

텍스트 값은 어쩌면 숫자보다도 컴퓨터 과학에서 더 근본적인 요소일 것이다. 이를 보여주는 좋은 예로, 파이썬 프로그램 자체가 텍스트로 작성되고 저장된다. 파이썬에서 텍스트를 다루는 원시 데이터 유형은 string이라고 불리며, str 생성자에 대응한다.

파이썬에서 문자열이 어떻게 표현되고, 작성되며, 조작되는지에 대한 세부 사항은 매우 방대하다. 문자열은 프로그래머가 마스터하기 위해 상당한 노력을 기울여야 하는 풍부한 추상화의 또 다른 예이다.

문자열 리터럴은 작은따옴표나 큰따옴표로 감싸서 임의의 텍스트를 표현할 수 있다.

우리는 이미 코드 내의 docstrings print호출 그리고 assert문의 에러 메세지 등에서 문자열을 보아왔다.

문자열은 이 장의 시작 부분에서 소개했던 시퀀스의 2가지 기본조건을 만족한다. 즉, 길이를 가지며 요소 선택을 지원한다.

문자열의 요소들은 그 자체로 단 하나의 글자만을 가진 문자열이다. character란 알파벳의 단일 문자, 문장 부호 등을 의미한다. 다른 많은 프로그래밍 언어와 달리, 파이썬에는 별도의 char 타입이 없다. 모든 텍스트는 문자열이며, 단일 문자를 나타내는 문자열은 길이가 1이다.

리스트와 마찬가지로 문자열 역시 덧셈과 곱셈을 통해 결합할 수 있다.

Membership 문자열의 행동은 파이썬의 다른 시퀀스 타입들과는 조금 다르게 흘러간다. 문자열 추상화는 우리가 리스트와 레인지에서 설명했던 완전한 시퀀스 추상화를 그대로 따르지는 않는다. 특히, 멤버십 연산자인 in은 문자열에도 적용되지만 일반적인 시퀀스에 적용될 때와는 완전히 다른 행동을 보인다. 문자열에서의 in은 개별 요소가 아니라 substring을 매칭한다.

Multiline Literals 문자열은 한 줄에만 국한되지 않는다. 삼중따옴표는 여러 줄에 걸쳐 있는 문자열 리터럴의 경계를 지정한다. 우리는 이미 독스트링을 작성할 때 이 삼중 따옴표를 광범위하게 사용해 왔다.

위의 출력 결과에서 \n은 줄바꿈을 나타내는 단일요소이다. 비록 \와 n이라는 두 개의 문자로 화면에 보이지만, 길이를 재거나 요소를 선택할 때는 단 하나의 문자로 간주된다.

String Coercion 파이썬의 임의의 객체를 인자로 하여 str 생성자 함수를 호출하면 어떤 객체로부터든 문자열을 생성할 수 있다. 문자열의 이러한 특징은 다양한 타입의 객체들로부터 설명이 담긴 문자열을 구축할 때 유용하다.

Trees

리스트의 요소로 또 다른 리스트를 사용할 수 있는 우리의 능력은 프로그래밍 언어에서 새로운 결합 수단을 제공한다. 이러한 능력을 데이터 타입의 폐쇄성이라고 부른다. 일반적으로 데이터 값들을 결합하는 방법이 폐쇄성을 갖는다는 것은, 결합의 결과물 또한 동일한 방법으로 다시 결합할 수 있음을 의미한다. 폐쇄성은 모든 결합 수단에서 힘의 핵심인데, 왜냐하면 우리로 하여금 계층적 구조를 만들 수 있게 해주기 때문이다.

우리는 환경 다이어그램에서 박스 앤 포인터 표기법을 사용하여 리스트를 시각화 할 수 있다. 리스트는 리스트의 요소를 포함하는 인접한 박스들로 묘사된다. 숫자, 문자열, 불리언 값, none과 같은 원시 값들은 요소 박스 내부에 나타난다. 함수 값이나 다른 리스트 같은 복합 값들은 화살표로 표시한다.

리스트 안에 리스트를 중첩하는 것은 복잡성을 유발할 수 있다. 트리는 계층적인 값들이 구조화되고 조작되는 방식에 규칙정을 부여하는 근본적인 데이터 추상화이다.

트리는 하나의 루트 레이블과 일련의 가지들의 시퀀스를 가진다. 트리의 각 가지는 그 자체로 트리이다. 가지가 없는 트리를 잎이라고 부른다. 트리 내부에 포함된 모든 트리를 그 트리의 서브트리라고 부른다. 트리의 각 서브트리의 루트를 그 트리의 노드라고 부른다.

트리를 위한 데이터 추상화는 생성자인 tree와 선택자인 label, branches로 구성된다. 먼저 단순화된 버전으로 시작해보자.

트리는 루트 레이블을 가지고 있고 모든 가지들 역시 트리인 경우에만 올바를 형태를 갖춘다. tree 생성자 내부에서 모든 가지가 올바른 형태인지 검증하기 위해 is_tree 함수가 적용된다.

is_leaf 함수는 트리에 가지가 있는지 없는지 확인한다.

트리는 중첩된 표현식으로 생성할 수 있다. 다음 트리 t는 루트 레이블이 3이고 2개의 가지를 가진다.

트리 재귀 함수를 사용하여 트리를 구성할 수 있다. 예를 들어 n번째 피보나치 트리는 n번째 피보나치 수를 루트 레이블로 가지며, n > 1일 때 역시 피보나치 트리인 2개의 가지를 가진다. 피보나치 트리는 피보나치 수의 트리 재귀적 계산 과정을 잘 보여준다.

트리 재귀 함수는 트리를 처리하는데도 사용된다. 예를 들어, count_leaves 함수는 트리의 잎 개수를 센다.

분할 트리 트리는 정수의 분할을 표현하는 데도 사용할 수 있다. 최대 크기 m이하의 인자들을 사용한 n의 분할 트리는 계산 과정 중에 이루어진 선택들을 나타내는 이진 트리이다.

잎 노드가 아닌 분할 트리에서

• 왼쪽가지는 적어도 하나의 m을 사용하여 n을 분할하는 모든 방법을 포함한다.
• 오른쪽 가지는 m-1 이하의 인자들을 사용한 분할을 포함한다.
• 루트 레이블은 m이 된다.

분할 트리의 잎 노드에 있는 레이블들은 루트에서 그 잎까지 이르는 경로가 n의 성공적인 분할을 나타내는지 여부를 표현한다.

분할 트리로부터 분할들을 출력하는 것은 트리를 순회하면서 각 분할을 리스트로 구축하는 또 다른 트리 재귀 과정이다. True인 잎에 도달할 때마다 해당 분할이 출력된다.

트리의 가지를 다룰 때도 슬라이싱을 사용할 수 있다. 예를 들어, 우리는 트리가 가질 수 있는 가지의 수에 제한을 두고 싶을 수 있다. 이진 트리는 잎 노드이거나, 최대 2개의 이진 트리로 이루어진 시퀀스이다. 이진화라고 불리는 흔한 트리 변환 기법은 인접한 가지들을 서로 묶어줌으로써 원래 트리로부터 이진 트리를 계산해 낸다.

Linked Lists

지금까지 우리는 시퀀스를 표현하기 위해 원시 데이터 유형만을 사용해왔다. 하지만 파이썬에 내장되어 있지 않은 새로운 시퀀스 표현을 직접 개발할 수도 있다. 중첩된 쌍으로 구성된 시퀀스의 흔한 표현 방식을 연결 리스트라고 부른다. 아래의 환경 다이어그램은 1,2,3,4를 포함하는 4개 요소 시퀀스의 연결 리스트를 보여준다.

연결 리스트는 시퀀스의 첫 뻔째 요소와 시퀀스의 나머지 부분을 포함하는 하나의 쌍이다. 두번쨰요소 역시 연결 리스트이다. 오직 4만을 포함하고 있는 가장 안쪽 연결 리스트이 나머지 부분은 빈 연결 리스트를 나타내는 값인 empty가 된다.

연결 리스트는 재귀적 구조를 가진다. 연결 리스트의 나머지 부분은 또 다른 연결리스트 이거나 empty이다. 우리는 연결 리스트의 성분들을 검증하고, 생성하고, 선택하기 위한 추상 데이터 표현을 정의한다.

위 코드에서 link는 생성자이고, first와 rest는 연결 리스트의 추상 데이터 표현을 위한 선택자이다. 연결 리스트의 동작 조건은 쌍과 마찬가지로 생성자와 선택자가 역함수 관계에 있어야 한다는 점이다.

만약 연결 리스트 s가 첫번째 요소 f와 연결 리스트 r로부터 생성되었다면 first(s)는 f를 반환하고 rest(s)는 r을 반환해야 한다.

이러한 종류의 추상 데이터를 구현할 때 우리는 2개의 요소를 가진 리스트 값을 쌍으로 사용했다. 앞서 함수만을 사용해서도 쌍을 구현할 수 있었음을 떠올려 보면, 어떤 방식의 쌍이든 상관없이 연결 리스트를 구현할 수 있으므로, 결과적으로 오직 함수만으로도 연결 리스트를 구현할 수 있다.

연결리스트는 값들의 시퀀스를 순서대로 저장할 수 있지만, 이것이 시퀀스 추상화를 만족한다는 것을 아직 보여주지 않았다. 우리가 정의한 추상 데이터 표현을 사용하면 시퀀스의 특징을 짓는 두 가지 행동인 길이와 요소 선택을 구현할 수 있다.

이제 우리는 이 함수들을 사용하여 연결 리스트를 하나의 시퀀스로 다룰 수 있다.

아래의 일련의 환경 다이어그램들은 getitem_link가 연결 리스트의 인덱스 1에서 요소 2를 찾아내는 반복과정을 보여준다. 다이어그램을 단순화하기 위해 아래 예시에서는 파이썬 원시 타입을 사용해 연결 리스트 four를 직접 정의했다. 이 방식은 추상화 장벽을 위반하는 선택이지만, 이번 예제에서 계산 과정을 더 쉽게 관찰할 수 있도록 도와준다.

먼저 getitem_link 함수가 호출되면서 로컬 프레임이 생성된다.

while 헤더의 표현식이 참이므로 while 코드블럭 내의 할당문이 실행된다. rest 함수는 2로 시작하는 서브리스트를 반환한다.

그다음 로컬 이름 s는 원래 리스트의 두 번째 요소로 시작하는 서브리스트를 가리키도록 업데이트된다. 이제 while 헤더 표현식을 평가하면 거짓(False) 값이 나오므로, 파이썬은 getitem_link 마지막 줄의 return 문에 있는 표현식을 평가한다.

이 최종 환경 다이어그램은 first 호출을 위한 로컬 프레임을 보여주며, 이 프레임은 동일한 서브리스트에 바인딩된 이름 s를 포함하고 있다. first 함수는 값 2를 선택하여 반환하며, 이 값은 getitem_link로부터도 최종 반환된다.

이 예제는 연결 리스트를 사용한 공통적인 계산 패턴을 보여준다. 반복의 각 단계는 원래 리스트에서 점점 더 짧아지는 접미사(suffix) 위에서 동작한다. 연결 리스트의 길이와 요소를 찾기 위해 이처럼 점진적인 처리를 수행하는 것은 계산하는 데 어느 정도 시간이 걸린다. 파이썬의 내장 시퀀스 타입들은 시퀀스의 길이를 계산하거나 요소를 검색할 때 큰 비용이 들지 않는 다른 방식으로 구현되어 있다.

Recursive manipulation len_link와 getitem_link는 모두 반복문(iterative) 기반이다. 이들은 리스트의 끝에 도달하거나(len_link), 원하는 요소에 도달할 때까지(getitem_link) 중첩된 쌍의 레이어를 하나씩 벗겨낸다. 우리는 길이와 요소 선택을 재귀(recursion)를 사용해서도 구현할 수 있다.

이 재귀적 구현들은 리스트의 끝에 도달하거나(len_link_recursive), 원하는 요소에 도달할 때까지(getitem_link_recursive) 쌍의 사슬을 따라간다.

재귀는 연결 리스트를 변형하고 결합하는 데도 매우 유용하다.

Recursive Construction 연결 리스트는 재귀 계산에서 자주 발생하는 상황처럼 시퀀스를 점진적으로 구성(construct)할 때 특히 유용하다. 1장에서 다루었던 count_partitions 함수는 트리 재귀 과정을 통해 최대 크기 m 이하의 인자들을 사용하여 정수 n을 분할하는 방법의 수를 세었다. 시퀀스를 사용하면 유사한 과정을 통해 이러한 분할들을 명시적으로 열거(enumerate)할 수도 있다. 우리는 가짓수를 셀 때와 동일한 재귀적 문제 분석을 따른다.

최대 m 이하의 정수를 사용하여n을 분할하는 것은 다음 중 하나를 포함한다.

1. 최대 m 이하의 정수를 사용하여 n-m을 분할하는 것, 또는
2. 최대 m-1 이하의 정수를 사용하여 n을 분할하는 것.

기본 케이스의 경우, 0은 하나의 빈 분할(empty partition)을 가지는 반면, 음의 정수를 분할하거나 1보다 작은 인자를 사용하는 것은 불가능하다.

재귀적인 경우, 우리는 두 개의 분할 서브리스트를 구성한다. 첫 번째는 $m$을 사용하는 경우이므로, using_m 결과의 각 요소 앞에 $m$을 추가(prepend)하여 with_m을 형성한다. partitions의 결과는 고도로 중첩되어 있다. 연결 리스트들의 연결 리스트이며, 각 연결 리스트는 리스트 값인 중첩된 쌍으로 표현된다. 적절한 구분 기호를 가진 join_link를 사용하면 분할들을 사람이 읽을 수 있는 방식으로 표시할 수 있다.