NEPLg2 Tutorial - 18 - 再帰と停止条件
Web Playground
Web Playground

再帰さいきと停止ていし条件じょうけん

NEPLg2 でも、関数は自分自身を呼び出せます。
ただし再帰では、必ず停止条件（base case）を先に明確にします。

sum_to を再帰で実装する

sum_to n は 1 + 2 + ... + n を返します。
n <= 0 を停止条件にして、無限再帰を防ぎます。

TEST
#entry main
#indent 4
#target std

#import "core/math" as *
#import "core/result" as *
#import "std/test" as *

fn sum_to <(i32)->i32> (n):
    if:
        cond le n 0
        then 0
        else:
            let prev <i32> sub n 1
            add n sum_to prev

fn main <()*>i32> ():
    let checks <Vec<Result<(),str>>>:
        checks_new
        |> checks_push check_eq_i32 0 sum_to 0
        |> checks_push check_eq_i32 1 sum_to 1
        |> checks_push check_eq_i32 15 sum_to 5
    let shown <Vec<Result<(),str>>> checks_print_report checks;
    checks_exit_code shown
ret0

条件分岐を if: で分けて書く

処理が長くなる場合は if: 形式にすると読みやすくなります。

TEST
#entry main
#indent 4
#target std

#import "core/math" as *
#import "core/result" as *
#import "std/test" as *

fn fib <(i32)->i32> (n):
    if:
        cond le n 1
        then n
        else:
            let n1 <i32> sub n 1
            let n2 <i32> sub n 2
            let a <i32> fib n1
            let b <i32> fib n2
            add a b

fn main <()*>i32> ():
    let checks <Vec<Result<(),str>>>:
        checks_new
        |> checks_push check_eq_i32 0 fib 0
        |> checks_push check_eq_i32 1 fib 1
        |> checks_push check_eq_i32 8 fib 6
    let shown <Vec<Result<(),str>>> checks_print_report checks;
    checks_exit_code shown
ret0

実装上の注意

  • 停止条件がない再帰は、実行時に停止しません。
  • 再帰を深くしすぎるとスタックを使い切ることがあります。
  • 深いループ処理は while に切り替える設計も検討します。