「再帰的」と「帰納的」

「再帰的」：記述のありよう。名前の出現

「帰納的」：もののありよう。構成の方法

https://youtu.be/ZP8u0QZ6514?t=224

もう一つの区別

"Algorithm Design with Haskell"

§ 1.3 Inductive and recursive definitions

While most functions make use of recursion, the nature of the recursion is different in different functions. The functions map, ﬁlter, and foldr all make use of structural recursion. That is, the recursion follows the structure of lists built from the empty list [] and the cons constructor (:). There is one clause for the empty list and another, recursive clause for x : xs in terms of the value of the function for xs. We will call such deﬁnitions inductive deﬁnitions. Most inductive deﬁnitions can be expressed as instances of foldr. For example, both map and ﬁlter can be so expressed.

code:haskell

perms₁ :: a -> a

perms₁ [] = [[]]

perms₁ (x:xs) = zs | ys <- perms₁ xs, zs <- inserts x ys

inserts :: a -> a -> a

inserts x [] = x

inserts x (y:ys) = (x:y:ys) : map (y:) (inserts x ys)

code:haskell

perms₁ = foldr step [[]]

where

step x xss = concatMap (inserts x) xss

code:haskell

perms₁ = foldr (concatMap . inserts) [[]]

Here is another way of generationg permutations, one that is recursive rather than inductive:

code:haskell

perms₂ :: a -> a

perms₂ [] = [[]]

perms₂ xs = x:zs | (x,ys) <- picks xs, zs <- perms₂ ys

picks :: a -> [(a,a)

picks [] = []

picks (x:xs) = (x,xs) : (y,x:ys) | (y,ys) <- picks xs

The different styles, recursive or inductive, of the deﬁnitions of basic combinatorial functions, such as permutations, partitions, or subsequences, lead to different kinds of ﬁnal algorithm. For example, divide-and-conquer algorithms are usually recursive, while greedy and thinning algorithms are usually inductive. To appreciate that there may be different algorithms for one and the same problem, one has to go back to the deﬁnitions of the basic functions used in the speciﬁcation of the problem and see if they can be deﬁned differently. For example, the inductive deﬁnition of perms₁ leads to Insertion sort, while the recursive deﬁnition of perms₂ leads to Selection sort.

code:haskell

perms₂ [] = [[]]

perms₂ xs = concatMap subperms (picks xs)

where

subperms (x,ys) = map (x:) (perms₂ ys)