2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

末尾再帰と再帰

Posted at

再帰関数

自分自身を呼び出す関数.
問題を小さな部分問題に分割し、それらを解決するために同じ関数を再帰的に呼び出す方法.

末尾再帰

再帰呼び出しがその関数の最後で行われる特殊な形式.
再帰呼び出しが他に何もせずにただ返される形.
→いくつかのプログラミング言語では最適化が行われ、スタックの使用量を削減できる可能

コード例

階乗計算:

再帰関数

function(n)
    if(n==1)
        return 1
else
    n*return function(n-1)

截屏2024-01-15 8.43.34.png
スタックの深さが増え続けると、スタックオーバーフローが発生し、プログラムが異常終了する可能。

末尾再帰関数

result=1
function(n,result)
    if(n==0)
        return result
    else
        return function(n-1,n*result)

截屏2024-01-15 8.43.44.png
スタックの使用を最小限に抑える効果がある(一部のプログラミング言語やコンパイラ)

C言語

C言語は末尾再帰関数を書けるが、最適化処理しない。スタックの使用量を削減するなどを実現できないはず。

2
1
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?