基礎編:再帰処理

#自己紹介
初めまして。
本誌を訪問頂き有難うございます。
趣味で python を始めた中年おじさんです。
基礎から始めたくて記事を書き始めた今日この頃です。
本誌は基礎編 第三弾です。

[**第一弾 基礎編:木構造の全探索(DFS/BFS)**](https://qiita.com/AKpirion/items/9a223254d628a5afca70)
[**第二弾 基礎編:基礎編:二分探索**](https://qiita.com/AKpirion/items/c70c55554ec187d2bf7e)

#学習目標
今回は [**Leetcode:Recursion I**](https://leetcode.com/explore/learn/card/recursion-i/) の理解を目標とします。
どのように理解するかは、以下のアプローチで進めます。

`テンプレートの暗記` =>
`記述の理解(イメージ作成)` => 
`自分なりのアプローチで再検証` => 
`理解の穴を埋める`

試行錯誤を繰り返すことで理解が深まり、思考力が養われると思います。

#例題1 [Reverse String](https://leetcode.com/explore/learn/card/recursion-i/250/principle-of-recursion/1440/)
文字列を反転できる機能を実装してください。

```answer_image.py
#Example 1:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
#Example 2:
Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]
```

##解説
純粋に反転するなら以下の記述が簡潔です。

```ReverseChar.py
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()
```

再帰処理であれば以下です。

```ReverseChar.py
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        def helper(left,right):
            if left < right:
                s[left],s[right] =s[right],s[left]
                helper(left+1,right-1)
        
        helper(0,len(s)-1)
        
```

この再帰的な記述は用途は不明ですが、
def reverseString に文字列を入れたら
反転した文字列を出力できた方が良いと思います。
別解もセットで考えなおしました。

```ReverseChar.py
class Reverse:
    def Approach1(nums):
        left,right = 0,len(nums)-1
        while left < right:
            nums[left],nums[right] = nums[right],nums[left]
            left +=1
            right -=1
        return nums

    def Approach2(nums):
        def helper(left,right):
            if left < right:
                helper(left+1,right-1)
                nums[left],nums[right] = nums[right],nums[left]
            return nums
        return helper(0,len(nums)-1)
       
nums =['a','b','c','d','e','f','g','h','i','j']

#-select approach-
#-----------------
#1.iterative
#print(Reverse.Approach1(nums))
#2.recursive
print(Reverse.Approach2(nums))

```

Recursive に関しては基本かもしれませんが、
逆転できる最下層まで一旦潜った後に、中央から left,right を反転し、
上位層に戻って反転を繰り返すことで意図した出力になります。

#例題2 [Swap Nodes in Pairs](https://leetcode.com/explore/learn/card/recursion-i/250/principle-of-recursion/1681/)
Given a linked list, swap every two adjacent nodes and return its head.
与えられた linked list で 2 ノードずつ逆転させて、その head を返してください。
 
```answer_image.py
#Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
#Example 2:
Input: head = []
Output: []
#Example 3:
Input: head = [1]
Output: [1]
```

制約:
The number of nodes in the list is in the range [0, 100].
0 <= Node.val <= 100

##解説
ノードの値を反転させる場合は、
head を格納する箱を 2 つ用意する必要があります。
これは、一方に格納した head の値を、もう一方の head に繋ぎあわせる作業を
繰り返すことで求められている回答を output するためです。
回答のコードと、その動きを追うための GIF を用意しました。

```SwapNode.py
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        first_node = head
        second_node= head.next
        
        first_node.next = self.swapPairs(second_node.next)
        second_node.next=first_node
        return second_node
```

![SwapNode.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/af9185b0-c659-0df7-0502-a83b2ccbd073.gif)

#例題3 [Pascal's Triangle](https://leetcode.com/explore/featured/card/recursion-i/251/scenario-i-recurrence-relation/1644/)
パスカルの三角形において f(5,3) の値を求めてください。
※個人的に面白かったので掲載します。

##解説
leetcode 先生のありがたい教えを賜ることが出来ました。
再帰処理を組む前に大事なことが 2 つあるそうです。

1.漸化式の定義
2.終点の定義

本件に当てはめて考えてみると、
以下のようになると思います。

1.漸化式 : f(i,j) = f(i-1,j-1) + f(i-1,j)
2.終点   : i == 1 or j == 1 or i == j の時、f(i,j) == 1

これを念頭にコードを書いてみます。

```PascalsTriangle.py
def pascal(i,j):
    if i == 1 or j == 1 or i == j:
        return 1
    return pascal(i-1,j-1)+pascal(i-1,j)
```

```実行結果.py
print(pascal(5,3))
#output : 6
```

先生の説明にもありますが重複した計算を行わなければならないのが
欠点になります。しっかり計算済みの物は保存して計算を最適化しましょうとのことです。
後の方で出てくるそうです。。。
また、この方法では後程出てくる問題は時間が掛かり過ぎて fail しますので注意が必要です。

#演習1 [Reverse Linked List](https://leetcode.com/explore/learn/card/recursion-i/251/scenario-i-recurrence-relation/2378/)
linked list を逆転させてください。

```answer_image.py
#Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
```
コメント:
iteratively or recursively のいずれでも解けます. 両方できますか?

##解説
iteratively を取り急ぎやってみました。
ざっくり以下のイメージで書いています。

`POINT1. head から val を取り出して q =[] に格納する`
`POINT2. q の値をもとに LinkList を作り直す`

```Reverse_LinkedList.py
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        #POINT1
        q =[]
        while head:
            q.append(head.val)
            head = head.next
            
        q.reverse()

        #POINT2
        root = None
        while q:
            nums = q.pop(0)
            if not root:
                root = ListNode(nums)
            else:
                runner = root
                while runner.next:
                    runner = runner.next
                runner.next = ListNode(nums)
        return root
```

recursively approach も挑戦してみましたが、
LinkedList の circle がイメージ出来ないと厳しいようです。
自分なりに情報取集してみました。

[**Design Linked List**](https://leetcode.com/explore/learn/card/linked-list/209/singly-linked-list/1290/)
`基礎の見直しと、特に Delete のイメージが circle を作る時に役に立ちます。`

[**Linked List Cycle**](https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1212/)
`与えられた LinkedList に circle が含まれているかを確認する問題で、チャレンジ & 解説を読むと good`

```ReverseLinkedList.py
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        p = self.reverseList(head.next)
        head.next.next = head # make cycle
        head.next = None      # remove cycle
        return p
```
前述にある make cycle でサイクルを作っています。
p は、名称は p ですが、中身は head です。
そのため　#make cycle , #remove cycle の記述にある 
head を編集する記述を適用することが出来るようです。

**[LinkedList: 1 -> 2 の場合]**
![ReverseLinkedList_case1.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/a1178940-162f-e812-a6b8-4abd0f30716e.gif)
**[LinkedList: 1 -> 2 -> 3 の場合]**
![ReverseLinkedList_case2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/35a6ccce-6ab4-9172-94cd-7265dbaafc8d.gif)

#演習2 [Search in a Binary Search Tree](https://leetcode.com/explore/learn/card/recursion-i/251/scenario-i-recurrence-relation/3233/)
BST と 整数をお渡しします。
整数が BST に含まれているか確認をお願いいたします。
含まれていれば、その値を起点とした部分木の値を全て返してください。
もし、こちらが指定した整数が含まれていなければ null を返してください。

```answer_image.py
#Example 1:
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
#Example 2:
Input: root = [4,2,7,1,3], val = 5
Output: []
``` 

制約:
ノード数は 1 ~ 5000。
ノードで格納されるデータは 1 以上 10^7 以下
与えられた Tree は必ず二分探索義

##解説
 
```SearchInBST.py
class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if root is None or val == root.val:
            return root
        
        return self.searchBST(root.left, val) if val < root.val \
            else self.searchBST(root.right, val)
```

#演習3 [Pascal's Triangle II](https://leetcode.com/explore/learn/card/recursion-i/251/scenario-i-recurrence-relation/3234/)
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
![PascalTriangleAnimated2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/0140a375-2df0-d297-0b77-2ce44ce51a0d.gif)

```answer_image.py
#Example 1:
Input: rowIndex = 3
Output: [1,3,3,1]
#Example 2:
Input: rowIndex = 0
Output: [1]
#Example 3:
Input: rowIndex = 1
Output: [1,1]
```

##解説
Iterative ですが、BSF の要領で解いてみました。

```PascalsTriangleII_O(n^2).py
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        ans =[]
        for i in range(rowIndex+1):
            ans.append([])
            for j in range(i+1):
                if j == 0 or j == i:
                    ans[i].append(1)
                else:
                    ans[i].append(ans[i-1][j-1]+ans[i-1][j])
                    
        return ans[rowIndex]
```

Recursive も出来たのですが、
Time over になりました。JAVA なら、この記述でもいけるのに(泣

```PascalsTriangleII_time_over.py
class Solution:
    def getNum(row,col):
        if row == 0 or col == 0 or row == col:
            return 1
        return Solution.getNum(row-1,col-1)+Solution.getNum(row-1,col)
    
    def getRow(self, rowIndex: int) -> List[int]:
        ans = []
        for i in range(rowIndex+1):
            ans.append(Solution.getNum(rowIndex,i))
        return ans
```

因みに時間は掛かりますが、後述している memorization の考え方を導入すると通ります。

```PascalsTriangleII_memorization.py
#164ms
import numpy as np

class Solution:
    def getNum(row,col):
        memo = np.zeros((34,34),dtype = "int")
        def helper(row,col):
            if memo[row][col] != 0:
                return memo[row][col]
            
            if row == 0 or col == 0 or row == col:
                result =  1
            else:
                result = helper(row-1,col-1)+helper(row-1,col)
                
            memo[row][col] = result
            return result
        return helper(row,col)
    
    def getRow(self, rowIndex: int) -> List[int]:
        ans = []
        for i in range(rowIndex+1):
            ans.append(Solution.getNum(rowIndex,i))
        return ans
```

recursive かつ時間に拘るなら以下のような記述も
あるようです(もっとシンプルに書けないのかなー)。

```PascalsTriangleII_case1.py
#12ms
class Solution:
    def getRowHelper(self, row, rowList, currentList):
        if row == 0:
            return
        if row == 1:
            return
        self.getRowHelper(row-1, rowList, currentList)
        for i in range(1, row):
            rowList[i] = currentList[i-1] + currentList[i]
        currentList[:] = rowList[:]
        return

    def getRow(self, rowIndex: int) -> List[int]:
        totalNumber = rowIndex + 1
        rowList = [1]*totalNumber
        currentList = [1]*totalNumber
        self.getRowHelper(rowIndex, rowList, currentList)
        return rowList
```

#演習4 [Fibonacci Number](https://leetcode.com/explore/learn/card/recursion-i/255/recursion-memoization/1661/)
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, 
such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).

```answer_image.py
#Example 1:
Input: n = 2
Output: 1
#Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
#Example 2:
Input: n = 3
Output: 2
#Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
#Example 3:
Input: n = 4
Output: 3
#Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.
```

##解説
再帰処理の欠点として重複計算が挙げられます。
これにより、処理時間が大幅に増えるケースがあることが挙げられます。
これを改善するために重複箇所はメモしたところから取り出すことで
処理時間の改善を図ることが可能です。
![image_memorization.JPG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/737344/5f0f6bd5-d2e7-d2ef-e424-7ce65db2a595.jpeg)
上図の "memo 前" にあるように再帰処理をしてみると
全探索のイメージで重複計算も含めて全部計算しようとします。
では、その計算量は如何ほどなのでしょうか。

ご覧のとおり実行の工程をツリー化してみて分かるように二分木として判断されます。
例えば n = 4 で計算する場合、Tree の深さは 4 となります。
これは 2^n -1 になりますので、O(2^n) と判断されます。

一方で "memo 後"を見ていきましょう。
以下のコードを実行してみればわかると思いますが、
fibo(n-1) + fibo(n-2) とあれば、左側の fibo(n-1) から再帰処理を解こうとします。
これは Binary Tree の inorder と同じような考え方で進んでいきます。
よって上図にあるように F(0) ~ F(3) まで演算した結果をメモしていきます。
その後発生する点線で表現された演算はメモから取り出すので演算は免除となります。
つまり計算量は n に依存するので O(n) となります。

詳細は [**Time Complexity - Recursion**](https://leetcode.com/explore/featured/card/recursion-i/256/complexity-analysis/1669/) から確認ができます。

```Fibonacci.py
class Solution:
    #796ms
    def fib_none_memo(self, N: int) -> int:
        if N <= 1:
            return N
        return self.fib_none_memo(N-1) + self.fib_none_memo(N-2)

    #24ms
    def fib_use_memo(self, N: int) -> int:
        cache = {}
        def helper(n):
            if n in cache:
                return cache[n]
            
            if n < 2:
                result = n
            else:
                result = helper(n-2) + helper(n-1)
            
            cache[n] = result
            return result
        return helper(N)
```

計算内容をメモしていく考え方は勿論 leetcode 先生の教えです。
[**memorization**](https://leetcode.com/explore/learn/card/recursion-i/255/recursion-memoization/1495/) をクリックすると詳細を確認することが可能です。
ハッシュを使った考え方がベースになるので hash の学習は必須になりそうです。

#演習5 [Climbing Stairs](https://leetcode.com/explore/learn/card/recursion-i/255/recursion-memoization/1662/)
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
 
```answer_image.py
#Example 1:
Input: n = 2
Output: 2
#Explanation: There are two ways to climb to the top.
#1. 1 step + 1 step
#2. 2 steps
#Example 2:
Input: n = 3
Output: 3
#Explanation: There are three ways to climb to the top.
#1. 1 step + 1 step + 1 step
#2. 1 step + 2 steps
#3. 2 steps + 1 step
```

##解説
一般的な再帰処理の解は time over となりうるのですが、
前述にある memorization を導入すると見事に通ります。

```ClimbingStairs.py
#28ms
class Solution:
    def climbStairs(self, n: int) -> int:
        cache = {}
        def helper(cnt,t1,t2,n):
            if n in cache:
                return cache[n]
            
            if n == 0:
                cnt += 1
                return cnt
        
            if 0 <= n-1:t1 = helper(cnt,t1,t2,n-1)
            if 0 <= n-2:t2 = helper(cnt,t1,t2,n-2)
            
            cache[n] =  t1 + t2
            return t1 + t2
        return helper(0,0,0,n)
```

#例題3 [RversePrinting](https://leetcode.com/explore/learn/card/recursion-i/256/complexity-analysis/2374/)
入力した文字を反転して出力してください。
アプローチは再帰処理でお願いいたします。

##解説
筆者の環境は Python 3 だからでしょうか。
以下のように修正しないと、こちらの環境では思うように動きませんでした。

```reversePrinting.py
def sum_non_tail_recursion(ls):
    if len(ls) == 0:
        return ""
    return sum_non_tail_recursion(ls[1:]) + ls[0]

def sum_tail_recursion(ls):
    def helper(ls, acc):
        if len(ls) == 0:
            return acc
        return helper(ls[1:], ls[0] + acc)
    return helper(ls, "")

ls = ["a","b","c","d"]

print(sum_non_tail_recursion(ls))
print(sum_tail_recursion(ls))
```

前述の解説 Tail recursion に素晴らしいことが記載されていました。
関数を call するときに現在の関数のパラメータとの演算をしている場合、
現在の関数の情報をメモリに残した状態で次の関数用のメモリを確保する必要があります。
しかし、再帰用に関数を call するときに現在の関数のパラメータとの演算なく、
関数の call だけで完結できれば既存のメモリ領域内で処理が完結するできるそうです。
すばらしい。

#例題4 [Maximum Depth of Binary Tree](https://leetcode.com/explore/learn/card/recursion-i/256/complexity-analysis/2375/)
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

```answer_image.py
#Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: 3
#Example 2:
Input: root = [1,null,2]
Output: 2
#Example 3:
Input: root = []
Output: 0
#Example 4:
Input: root = [0]
Output: 1
```

##解説
これは過去に解いている問題で、Tree の深さを求める問題です。
例題3 にあったように leetcode 先生の教えから none tail , tail で解いて比較してみました。

```maxDepth.py
class Solution:
    #run time : 48ms
    #memory usage : 18.8MB    
    def maxDepth_none_tail(self, root: TreeNode) -> int:
        def helper(l,r):
            if not root:
                return 0
        
            if root.left: l = self.maxDepth_none_tail(root.left) + 1
            if root.right:r = self.maxDepth_none_tail(root.right)+ 1
            return max(l,r)
        return helper(1,1)

    #run time : 36ms
    #memory usage : 16.5MB   
    def maxDepth_tail(self, root: TreeNode) -> int:
        if not root:return 0
        def helper(node,cnt,l,r):
            if not node.left and not node.right:
                return cnt
            
            if node.left: l = helper(node.left,cnt+1,l,r)
            if node.right:r = helper(node.right,cnt+1,l,r)    
            cnt = max(l,r)
            return cnt
        return helper(root,0,0,0)+1

```

教えのとおりにメモリの使用率も減り、
その分、処理スピードも上がりました。


#演習6 [Merge Two Sorted Lists](https://leetcode.com/explore/learn/card/recursion-i/253/conclusion/2382/)
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

```answer_image.py
#Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
#Example 2:
Input: l1 = [], l2 = []
Output: []
#Example 3:
Input: l1 = [], l2 = [0]
Output: [0]
```

##解説

```MergeTwoSortedLists.py
class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2
```

#演習7 [K-th Symbol in Grammar](https://leetcode.com/explore/learn/card/recursion-i/253/conclusion/1675/)
On the first row, we write a 0. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

Given row N and index K, return the K-th indexed symbol in row N. (The values of K are 1-indexed.) (1 indexed).

```answer_image.py
#Examples1:
Input: N = 1, K = 1
Output: 0

Input: N = 2, K = 1
Output: 0

Input: N = 2, K = 2
Output: 1

Input: N = 4, K = 5
Output: 1

#Explanation:
#row 1: 0
#row 2: 01
#row 3: 0110
#row 4: 01101001
```

Note:
N will be an integer in the range [1, 30].
K will be an integer in the range [1, 2^(N-1)].

##解説

```K-thSymbolinGrammar.py
class Solution():
    def kthGrammar(self, N, K):
        if N == 1: return 0
        if K <= (2**(N-2)):
            return self.kthGrammar(N-1, K)
        return self.kthGrammar(N-1, K - 2**(N-2)) ^ 1
```

#演習8 [Unique Binary Search Trees II](https://leetcode.com/explore/learn/card/recursion-i/253/conclusion/2384/)
Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

```answer_image.py
#Example 1:
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
#Example 2:
Input: n = 1
Output: [[1]]
``` 

制約:
1 <= n <= 8

##解説

```UniqueBinarySearchTreeII.py
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def generate_trees(start, end):
            if start > end:
                return [None,]
            
            all_trees = []
            for i in range(start, end + 1):  # pick up a root
                # all possible left subtrees if i is choosen to be a root
                left_trees = generate_trees(start, i - 1)
                
                # all possible right subtrees if i is choosen to be a root
                right_trees = generate_trees(i + 1, end)
                
                # connect left and right subtrees to the root i
                for l in left_trees:
                    for r in right_trees:
                        current_tree = TreeNode(i)
                        current_tree.left = l
                        current_tree.right = r
                        all_trees.append(current_tree)
            
            return all_trees
        
        return generate_trees(1, n) if n else [] 
```