rubyで再帰関数

rubyで再帰の練習。
ネタはここを参考にさせていただきました

配列の和

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]