単純な再帰

再帰は Scheme の強力な概念であり、関数がそれ自体を呼び出して元の問題の小さなサブ問題を解決します。 単純な再帰 パターンには、再帰を停止する基本ケースと問題を軽減する再帰ケースが含まれます。

再帰関数の一般的な構造は次のようになります。

(define (function-name args)
  (if (base-condition)
    base-result
    (recursive-call)))

基本条件: 再帰を停止します。
基本結果: 基本条件が満たされた場合に返される値。
再帰呼び出し: 計算を基本ケースに近づける、変更された引数を使用した関数自体の呼び出し。

例: 数値の合計 (1 から n)

1 から n までの数値の合計を計算する単純な再帰関数:

(define (sum-to-n n)
  (if (= n 0)                  ; Base case: stop when n is 0
    0                          ; Base result: sum is 0
    (+ n (sum-to-n (- n 1))))) ; Recursive call: sum current n with result of smaller problem

仕組み: 分解と再組み立て

再帰は、元の問題をより小さな部分に分解することで機能します。関数の各呼び出しは 1 つの部分を処理し、残りを渡します。最も単純なケースに到達すると、計算が完了するにつれて結果が再組み立てされます。

sum-to-n 3 のステップバイステップトレース

最初の呼び出し: sum-to-n 3 → (+ 3 (合計を n 2))
2 回目の呼び出し: sum-to-n 2 → (+ 2 (n の合計 1))
3 回目の呼び出し: sum-to-n 1 → (+ 1 (合計を n 0))
基本ケース: sum-to-n 0 → 0

最終結果を再組み立てする

最も単純なケースが解決されると、計算の各層が完了します。

sum-to-n 0 は 0 を与えます
sum-to-n 1 は (+ 1 0) = 1 になります
sum-to-n 2 は (+ 2 1) = 3 になります
n の合計 3 は (+ 3 3) = 6 になります

例: リストの各要素の出力

以下は、リスト内のすべての要素を出力する単純な再帰関数です。

(define (print-elements lst)
  (if (null? lst)
    (lumi-message "done")
    (begin
      (lumi-message (number->string (car lst))) ; Print the first element
      (print-elements (cdr lst)))))             ; Process the rest of the list

基本ケース: リストが空の場合 (null? lst)、再帰を停止します。
再帰的な場合: 最初の要素 (car lst) を出力し、リストの残りの関数 (cdr lst) を呼び出します。

使用例

(print-elements (list 1 2 3))

出力:

「1」
「2」
「3」

結果: 「完了」

仕組み

この関数は car を使用してリストの最初の要素を取得し、それを処理します。
次に、リストの残りの部分を使用して自分自身を呼び出します (cdr)。
このプロセスは、リストが空になるまで (null? lst) 繰り返されます。

概要

単純な再帰は次のもので構成されます。
1. 基本ケース: 再帰を停止します。
2. 再帰的なケース: 基本ケースに向けて問題を軽減します。
各再帰呼び出しにより、完了に向けて計算が進行します。
基本ケースに到達すると、再帰が完了するにつれて結果が結合されます。

再帰は問題の構造を反映し、明確で論理的なフローを提供します。無限再帰を避けるために、常に基本ケースを確認してください。

それぞれに