再帰関数で組み合わせを選ぶアルゴリズムの意味が理解できないので教えてほしいです！

前提

再帰関数で以下の問題で模範コードの意味が知りたいです。

実現したいこと

以下に記載のコードの以下の部分の意味がよくわからいので噛み砕いて教えて抱きたいです。(当サイトの解説が乏しいため)

c++
1func(n-1,l+1,r) + func(n,l+1,r);

該当のソースコード

c++
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// 再帰関数 (N = n, L = l, R = r のときの問題の答え)
6int func(int n, int l, int r) {
7    // n = 0 のとき、答えは空配列のみ (1 つ)
8    if (n==0) return 1;
9
10    // l > r のとき、答えは存在しない
11    if (l>r) return 0;
12
13    // それ以外のとき
14    int ans = func(n-1,l+1,r) + func(n,l+1,r);
15
16    return ans;
17}
18
19int main() {
20    // 入力
21    int N, L, R;
22    cin >> N >> L >> R;
23
24    // 出力
25    int ans = func(N,L,R);
26    cout << ans << endl;
27}

input, output

input

2 1 3

output

行動規範の内容に同意します

回答1件

ベストアンサー

funcが呼ばれたとき、
左再帰項のfunc(n-1,l+1,r)ってのは、Aiをlと定めたとき、残りのAi+1..An-1までのパターン数。だから引数には nｰ1（Aの決まってない数は減る）、l+1（このlは使ったから）。
右再帰項のfunc(n,l+1,r)ってのは、Aiにlを使わないときのパターン数。だからｌだけ+1。
再帰なので、左で呼んだfuncでは「Ai+1をl＋1と定める」か「L+1を使わない」かに分かれていくし、右で呼んだfuncでは「AiをL＋1と定める」か「L+1を使わない」かに分かれていく。

具体的に書けばわかりやすいかも。
L=1, R=3, N=2のとき、こたえのパターンは1-2, 1-3, 2-3。再帰funcに呼び出し順で名前をつけておくと(func2は2回目に呼ばれたfunc、程度の意味）
func0左:a0=1を決定して、func1( N=1,L=2, R=3)を呼ぶ
+func1左：a1=2を決定して、func( N=0)でおしまい。＃1-2
+func1右：2は使わず、func2( N=1, L=3, R=3)を呼ぶ
++ func2左：a2=3を決定して、func( N=0)でおしまい。#1-3
++ func2左：3を使わないと、func( N=1, L=4, R=3)で無効
func0右:1を使わずfunc3( N=2, L=2, L=3)を呼ぶ
+func3左：a0=2を決定して、func4( N=1,L=3,R=3)を呼ぶ
++func4左：a1=3を決定して、func( N=0)でおしまい。#2-3
（略）