rubyで再帰関数

rubyで再帰の練習。
ネタは[ここ](http://bleis-tift.hatenablog.com/entry/20120119/1326944722)を参考にさせていただきました


#配列の和

```sum.rb
def sum(arr)
    return 0 if arr.empty? #配列が空のときは終了
    top = arr.shift
    top + sum(arr)
end
p sum([1,2,3,4,5]) #=> 15
```

#配列の長さ
```length.rb
def length(arr)
    return 0 if arr.empty? #配列が空のときは終了
    arr.shift
    1 + length(arr)
end

p length([1,2,3,4,5]) #=> 5
```

#配列内の最大値
```max.rb
def max(arr)
    return arr[0] if arr.length == 1 #数字が一つときはその一つが最大値    
    x = arr.shift  
    y = max(arr)
    x > y ? x : y                    #max()で返されるのは先頭要素以外の中での最大値なので、それと先頭要素を比べて大きい方を返す
end
p max([1,10,3,9,100,5]) #=> 100
```

#配列内の最少値
```min.rb
def min(arr)
    return arr[0] if arr.length == 1 #数字が一つとき（一番簡単な場合）はその一つが最少値    
    x = arr.shift  
    y = min(arr)
    x < y ? x : y                    #min()で返されるのは先頭要素以外の中での最少値なので、それと先頭要素を比べて少ない方を返せばいい
end
p min([1,10,3,9,100,5]) #=> 1
```

#すべての要素がブロックの条件を満たすかどうか
```forall.rb
def forall?(arr,&b)
    return true if arr.empty?       #全要素走査し終わった時や要素がない時はtrueを返す。
    top = arr.shift
    b.call(top) && forall?(arr,&b)  #すべて満たすか判定したいので && を使う。
end
odd = lambda{ |n| n % 2 == 0 }
p forall?([2,4,6],&odd)  #=> true
p forall?([2,1,6],&odd)  #=> false
```

#配列内に一つでもブロックの条件を満たすものがあるかどうか
```exists.rb
def exists?(arr,&b)
    return false if arr.empty?       #全要素走査し終わった時や要素がない時や要素がない時はfalseを返す。
    top = arr.shift
    b.call(top) || exists?(arr,&b)   #||なので、満たすものがあった時点でtrueが返る
end
even = lambda{ |n| n % 2 != 0 }
p exists?([2,4,6],&even) #=> false
p exists?([2,6,1],&even) #=> true
```

#条件がtrueとなるはじめの要素を返す
```find.rb
def find(arr,&b)
    return nil if arr.empty?  #要素がない時はnilを返す。    
    top = arr.shift
    b.call(top) ? top : find(arr,&b)
end

string = lambda{ |n| n.kind_of?(String) }
p find([1,2,"b",3,"c"],&string)  #=> b
```

#先頭から n 個捨てて、残った配列を返す。
```skip.rb
def skip(arr,n)
    return nil if arr.empty?       # n個捨てきる前に配列が空になったらはnilを返す。
    if n == 0                      # n個捨てきったら残りの配列を返す
        arr
    else
        arr.shift
        skip(arr,n - 1)
    end
end
p skip([1,2,3,4],2) #=> [3,4]
p skip([1,2],3)     #=> nil
p skip([],3)        #=> nil
```

#先頭から n 個の要素を取り出す
```take.rb
def take(arr,n,result=[])
    return result if arr.empty?      # n個取り出す前に配列が0になったらその時点での取り出し配列を返す。
    if n == 0                        # n個取り出しきったら、その取り出しきった配列を返す
        result
    else
        result << arr.shift
        take(arr,n - 1,result)
    end
end
p take([1,2,3,4,5,6,7],3) #=> [1, 2, 3]
p take([1,2],3)           #=> [1, 2]
p take([],3)              #=> []
```

#先頭から n 個の要素を取り出す。ただし取り出す条件の指定つき
```take_while.rb
def take_while(arr,n,result=[],&b)
    arr_copy ||= Array.new(arr)    #元の配列を壊さないようにコピー
    return result if arr_copy.length == 0
    if n == 0
        result
    else
        top = arr_copy.shift
        result << top if b.call(top)
        take_while(arr_copy,n - 1,result,&b)
    end
end
#先頭から4個までの間で5以上の値を取り出す
five_over = lambda{|n| n > 5}
arr = [1,10,6,4,2,3,6]
p take_while(arr,4,&five_over) #=> [10, 6]
p arr                          #=> [1, 10, 6, 4, 2, 3, 6]
```

#map
```map.rb
def map(arr,result=[],&b)
    return result if arr.empty?
    top = arr.shift
    result << b.call(top)
    map(arr,result,&b)
end
double = lambda{|n| n * 2 }
p map([1,2,3],&double)  #=> [2, 4, 6]
```

#条件を満たす要素のみを残した配列を返す
```filter.rb
def filter(arr,result=[],&b)
    arr_copy ||= Array.new(arr)    #元の配列を壊さないようにコピー
    return result if arr_copy.length == 0
    top = arr_copy.shift
    result << top if b.call(top)
    filter(arr_copy,result,&b)
end
arr = [100,2,1,33,50,51]
fifty_over = lambda{|n| n > 50}
p filter(arr,&fifty_over) #=> [100, 51]
p arr                     #=> [100,2,1,33,50,51]
```

#map と filter を一度に行う
例えば、「1, 2, 3, 4, 5」という列と「偶数は 2 倍して返す」関数を渡すと、「4, 8」という列が返ります。

```choose.rb
def choose(arr,result=[],&b)
    return result if arr.empty?
    top = arr.shift
    result << b.call(top) if b.call(top) #ブロックの結果がtrueな値だったら、その値をresultへ入れる。
    choose(arr,result,&b)
end
func = lambda{|n| 
    return n * 2 if n.even?
}
p choose([1,2,3,4,5],&func)  #=> [4, 8]
```

#条件を満たす要素の列と満たさない要素の列の両方を返す
```partition.rb
def partition(arr, satisfy=[],not_satisfy=[], &b)
    arr_copy ||= Array.new(arr)                                 #元の配列を壊さないようにコピー
    return satisfy,not_satisfy if arr_copy.length == 0          #全部の要素の走査が終わったら結果を返して終了
    top = arr_copy.shift
    if b.call(top)
        satisfy << top        #条件満たす場合はsatisfy配列へ入れる
    else
        not_satisfy << top    #条件満たさない場合はnot_satisfy配列へ入れる
    end
    partition2(arr_copy,satisfy,not_satisfy,&b)
end
#10を超える要素と超えない要素に分ける
ten_over = lambda{|n| n > 10}
arr = [100,2,1,33,50,51]
result = partition(arr,&ten_over)     
p result[0] #=> [100, 33, 50, 51]
p result[1] #=> [2, 1]
```

#階乗
```factorical.rb
def factorical(number)
  if number.zero?
    1
  else
    number * factorical(number - 1)
end
p factorical(3)                      #=> 6
```

#等差数列
```arithmetic_seq.rb
def arithmetic_seq(start,interval,n,result=[])
    return result if n == 0
    result << start
    start += interval
    arithmetic_seq(start,interval,n - 1,result)
end
p arithmetic_seq(2,2,5)  #=> [2, 4, 6, 8, 10]
```

#素数判定　メモ化
```prime.rb
def prime?(n)
    @cache ||= {}                          #計算済みのものをいれておくハッシュ
    return @cache[n] if @cache.has_key?(n) #すでに計算済みならそれを返す
    def divisible_count(target,n,count=0)
        return true if n == 0 && count == 2
        return false if n == 0
        count += 1 if target % n == 0
        divisible_count(target,n-1,count)
    end
    return false if n < 2                  #0と1は素数じゃないので計算するまでもない
    @cache[n] = divisible_count(n, n)
end
p prime?(47)   #=> true
p prime?(2203) #=> true
p prime?(5000) #=> false
```
#フィボナッチ　メモ化
```fibonacci.rb
def fibonacci(n)
  @cache ||= []  #計算済みのものをいれておく配列
  return n if n <= 1
  @cache[n] ||= fibonacci(n-1) + fibonacci(n-2)
  return @cache[n]
end
puts fibonacci(10) #=> 55
```

#バブルソート
配列の先頭から、二つの要素を比較する。順序が不正であれば入れ替える。
最後まで辿り着いたら、再び先頭から。1回のソートで最高点が右へいく。
一度も入れ替えが発生しなければソート完了。

```bubble_sort.rb
def bubble_sort(arr,size,idx=0)  #arrはソートする配列、sizeは探索範囲で初期値は配列のlength。idxは添え字。
    if size > 1 #sizeが 1 になったら終了。要素が一つということはソートするものがもうないということ。
        #ここのif内の処理で最高点が右端へ固定していく。
        if idx < size - 1  
            #隣り合う数字を比べて左が大きければ数字を交換する（大きい数字をひとつ右に移動させる）
            if arr[idx] > arr[idx + 1]
                arr[idx], arr[idx + 1] = arr[idx + 1], arr[idx]
            end
            #インデックスを1増やして再度隣り合う数字の比較を行っていく。
            bubble_sort(arr,size,idx + 1)
        end
        #添え字が探索範囲より大きい場合はここにくる。
        #ここに来るということは、最高点が右端に一つ固定できたということ。
        #なので、探索範囲をひとつ狭めて再度ソート。
        bubble_sort(arr, size - 1, 0);
    end
    arr
end
arr = [3,4,6,1,7,2]
p bubble_sort(arr,arr.length) #=> [1, 2, 3, 4, 6, 7]
```