常連

### 前提
フィボナッチ数列を用いてretutn文について学習しています。
下記のコードは、n番目の項の数字がprintされるもので、講師が書いたものです。

質問ですが、
**なぜ4を入力すると3が出力されるのかが、わかりません。**

nに4を入力した場合
fib(4 - 1) + fib(4 - 2)=fib(5)
そして、これを再帰処理し
fib(5 - 1) + fib(5 - 2)=fib(7)...
となるのが、私のreturn文に対する理解度での限界でした。
おそらく8行目の計算方法か、再帰処理の部分に間違いがあるのだと思います。


**どのようなアルゴリズムで3という出力がなされるのかを教えていただきたいです。**

とても初歩的な質問だとは思いますが、よろしくお願いします。


### 該当のソースコード

```Python
# n番目のフィボナッチ数を返す関数
def fib(n):
  # nが0または1の場合はそのまま返す
  if n == 0 or n == 1:
    return n
  # nが2以上の場合は再帰的に計算する
  else:
    return fib(n - 1) + fib(n - 2)

# 例: 10番目のフィボナッチ数を求める
print(fib(4)) #実行すると3が出力されます
```

pythonのreturn文、再帰処理に関する質問(フィボナッチ数列)

### 実現したいこと
- ハノイの塔を実行するプログラムをコーディングしたい。


### 前提

C言語でハノイの塔を実行するプログラムを書いています。
動作が目に見える形で出力されるインタラクティブなものを創っています。
### 発生している問題・エラーメッセージ

```
### start
0|6]5]4]3]2]1]
1|
2|
### move 0 to 1
0|6]5]4]3]2]
1|1]
2|
### verify: OK
### move 0 to 2
0|6]5]4]3]
1|1]
2|2]
### move 1 to 2
0|6]5]4]3]
1|
2|2]1]
### verify: OK
### verify: OK
### move 0 to 1
0|6]5]4]
1|3]
2|2]1]
### move 2 to 0
0|6]5]4]1]
1|3]
2|2]
### verify: FAILED
0|6]5]4]1]
1|3]
2|2]
```

### 該当のソースコード

```Ｃ
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define N_TOWER 3

unsigned* tower[N_TOWER];
unsigned* top[N_TOWER];
unsigned n_input;
unsigned n_steps = 0;

void print_tower(unsigned i) {
    assert(0 <= i && i < N_TOWER);
    unsigned* p = tower[i];

    printf("%d|", i);
    while (p != top[i]) {
        printf("%d]", *p);
        p++;
    }
    printf("\n");
}

void print_towers() {
    int i;
    for (i = 0; i < N_TOWER; i++) {
        print_tower(i);
    }
}

void move(unsigned from, unsigned to) {
    printf("### move %d to %d\n", from, to);
    unsigned disk = *(--top[from]);
    *(top[to]++) = disk;
    n_steps++;
    print_towers();
}

int verify_towers(unsigned* t0, unsigned* t1, unsigned* t2) {
    int j;
    for (j = 0; j < n_input - 1; j++) { //最大の高さのインデックス=(n_input-1)
        if (t0[j] < t0[j + 1] || t1[j] < t1[j + 1] || t2[j] < t2[j + 1]) {
            return 0; //ルールを無視している
        }
    }
    return 1; 
}

void hanoi(unsigned n, unsigned cur_pos, unsigned dest_pos) { //current,destination
    assert(0 < n);
    assert(0 <= cur_pos && cur_pos < N_TOWER);
    assert(0 <= dest_pos && dest_pos < N_TOWER);

    if (n == 1) {
        move(cur_pos, dest_pos);
    }
    else {
        unsigned tmp_pos = 3 - cur_pos - dest_pos; //temporary、仮の保管場所
        hanoi(n - 1, cur_pos, tmp_pos);
        move(cur_pos, dest_pos);
        hanoi(n - 1, tmp_pos, dest_pos);
    }

    if (verify_towers(tower[0], tower[1], tower[2]) &&
        verify_towers(tower[0], tower[1], tower[2]) &&
        verify_towers(tower[0], tower[1], tower[2])) {
        puts("### verify: OK");
    }
    else {
        puts("### verify: FAILED");
        print_towers();
        exit(EXIT_FAILURE);
    }
}


int main(int argc, char** argv) {
    int i;

    assert(argc == 2);
    n_input = atoi(argv[1]);
    assert(n_input > 0);

    for (i = 0; i < N_TOWER; i++) {
        tower[i] = malloc(n_input * sizeof(unsigned));
        if (tower[i] == NULL) exit(EXIT_FAILURE);
        top[i] = tower[i];
    }
    for (i = 0; i < n_input; i++) {
        *top[0] = n_input - i;
        top[0]++;
    }

    puts("### start");
    print_towers();
    hanoi(n_input, 0, 2);
    printf("### %d steps to complete\n", n_steps);

    return 0;
}

```

### 試したこと

verify_towers関数を確認してみましたが、エラーとなる原因を見つけることができませんでした。

### 補足情報（FW/ツールのバージョンなど）

Linuxの端末


ハノイの塔を実行するプログラム

初歩的な質問で恐縮ですが、ご教示下さい。

cpコマンドのオプション「-r」を使用した再帰的なコピーですが、これまで「ディレクトリを丸っとコピーする」的なあいまいな解釈で使用してきました。
改めて「再帰的」に向き合ってみようと思いましたが、頭の中で整理することができません。

例えば、以下のようなディレクトリ構成の場合で、
```Linux
ls -R /home/hoge/
/home/hoge/:
dir1  dir2

/home/hoge/dir1:
aaa.txt  bbb.txt

/home/hoge/dir2:
```
以下の再帰的コピーコマンドを実行します。
```Linux
cp -r /home/hoge/dir1/ /home/hoge/dir2/
```
すると以下のディレクトリ構造となります。
```Linux
ls -R /home/hoge/
/home/hoge/:
dir1  dir2

/home/hoge/dir1:
aaa.txt  bbb.txt

/home/hoge/dir2:
dir1

/home/hoge/dir2/dir1:
aaa.txt  bbb.txt
```
これまでの「ディレクトリを丸っとコピーする」という解釈では上記の構造となるのは納得できるのですが、私の「再帰的」という動作の解釈は以下です。
> まず、ディレクトリ内に存在するものに一つ一つに対して処理をする。
その際、その一つがディレクトリだったら、
そのディレクトリ内に存在するものに一つ一つに対して処理をする。
その際、その一つがディレクトリだったら...

上記の解釈だと、先程の再帰的コピーコマンドは以下の処理が実行されるのと同義ではないかと思いました。
```Linux
cp -r /home/hoge/dir1/ /home/hoge/dir2/
↓
1. まず/home/hoge/dir1/ディレクトリ(のみ)を /home/hoge/dir2/にコピー
2. dir1ディレクトリ内のファイル aaa.txt に同様の処理、つまり cp /home/hoge/dir1/aaa.txt /home/hoge/dir2/
3. dir1ディレクトリ内のファイル bbb.txt に同様の処理、つまり cp /home/hoge/dir1/bbb.txt /home/hoge/dir2/
```
しかし当たり前ですが上記1〜3の処理では再帰的コマンド実行時と同様の結果になりません。
(dir2ディレクトリ直下に 空のdir1ディレクトリ、aaa.txt、bbb.txt が存在する状態になる)

そもそも再帰的コマンドを分解して解釈しようとするのがご法度なのかもしれませんが、、、
すみません。「そういうものだよ」と納得するのが悔しく、ちゃんと「再帰的」と向き合いたいと思いご質問させていただきました。

以上、「再帰的」の捉え方について良い解釈がございましたらご教示いただけますと幸いです。

cpコマンドオプション「-r」の再帰的について

### 実現したいこと

- ある問題を動的計画で解いた場合とメモ化再帰で解いた場合とで、実行時間にどの程度差が生じるのか知りたい。

### 前提

私は動的計画法について勉強中で、atcoder内の以下の問題に取り組んでいます。
URL: https://atcoder.jp/contests/dp/tasks/dp_i
~~~
実行時間制限: 2 sec / メモリ制限: 1024 MB
**問題文**
N を正の奇数とします。
N 枚のコインがあります。 コインには 1,2,…,N と番号が振られています。 
各 i (1≤i≤N) について、コイン i を投げると、確率 p_iで表が出て、確率 1−p_i で裏が出ます。
太郎君は N 枚のコインをすべて投げました。 このとき、表の個数が裏の個数を上回る確率を求めてください。

**制約**
- N は奇数である。
- 1 ≤ N ≤ 2999
- p_i は実数であり、小数第 2 位まで与えられる。
- 0 < p_i <1

**入力**
入力は以下の形式で標準入力から与えられる。
N
p_1
​p_2
… 
p_N
​
**出力**
表の個数が裏の個数を上回る確率を出力せよ。 絶対誤差が 10^(−9) 以下ならば正解となる。
 ~~~

### 質問
この問題を動的計画とメモ化再帰で解く2つのプログラムをそれぞれ作成したのですが、動的計画では任意の入力に対して100 msec以内で終了するのに対して、メモ化再帰の場合は制限時間の2 sec を超過してしまいます。

動的計画とメモ化再帰の違いに関して、
- ボトムアップかトップダウンどちらで最終的な解答を得ようとするかの違いはあるものの、内部の計算は似たもの
- メモ化再帰では関数を繰り返し呼び出すことによるオーバヘッドが生じるため、動的計画よりは遅くなる可能性がある
と理解しているのですが、それだけで実行時間にここまで大きな差が生まれるものなのでしょうか？
それとも、私のメモ化再帰の実装が悪いために遅くなってしまっているのでしょうか？

ぜひ、教えていただければ幸いです。


### 動的計画にもとづくプログラム

```C++
#include <iomanip>
#include <iostream>
#include <vector>

int main() {
    int N;
    std::cin >> N;
    std::vector<double> p(N, 0.0);
    for (int i = 0; i < N; i++) {
        std::cin >> p[i];
    }

    std::vector<std::vector<double>> dp(N + 1, std::vector<double>(N + 1, 0.0));
    dp[0][0] = 1.0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i + 1][j] += dp[i][j] * (1.0 - p[i]);
            dp[i + 1][j + 1] += dp[i][j] * p[i];
        }
    }

    double res = 0.0;
    for (int i = N / 2 + 1; i <= N; i++) {
        res += dp[N][i];
    }

    std::cout << std::fixed << std::setprecision(10) << res << std::endl;

    return 0;
}
```
### メモ化再帰にもとづくプログラム

```C++
#include <iomanip>
#include <iostream>
#include <vector>

int N;
std::vector<double> p(10000, 0.0);
std::vector<std::vector<double>> dp(10000, std::vector<double>(10000, 0.0));

double rec(int i, int j) {
    if (dp[i][j] != 0.0) {
        return dp[i][j];
    }
    if (i == 0 and j == 0) {
        return 1.0;
    }
    if (i < j) {
        return 0.0;
    }
    if (i > 0 and j == 0) {
        return dp[i][j] += rec(i - 1, j) * (1.0 - p[i - 1]);
    }
    return dp[i][j] += rec(i - 1, j) * (1.0 - p[i - 1]) + rec(i - 1, j - 1) * p[i - 1];
}

int main() {
    std::cin >> N;
    for (int i = 0; i < N; i++) {
        std::cin >> p[i];
    }

    double result = 0.0;
    for (int j = N / 2 + 1; j <= N; j++) {
        result += rec(N, j);
    }

    std::cout << std::fixed << std::setprecision(10) << result << std::endl;

    return 0;
}
```



AtcoderのEducational DP Contestの問題 I - Coins を動的計画で解いた場合とメモ化再帰で解いた場合の実行時間の違いについて

### 実現したいこと
PythonにてDFS（再帰）を用いて、特定の条件を満たすルートを全て洗い出したいです。

### 前提

Atcoder で以下の問題をDFS（再帰）を用いて解きたいと考えています。
https://atcoder.jp/contests/abc293/tasks/abc293_c

### 発生している問題・エラーメッセージ
下に自分の書いたコードを添付します。
17行目で”ゴールに辿り着いた際、一段階戻って他の経路の探索を続ける”ことができないです。
ですが、returnを取り外すと継続できます。
また13行目で行っている、”条件に合わなかった場合、一段階戻って他の経路の探索を続ける”についてはreturnがついていても可能です。
これはなぜなのでしょうか。
returnにはどのようなルールがあるのか理解できずにいます。


### 該当のソースコード

```python
import sys
 
sys.setrecursionlimit(10**7)

H, W = map(int, input().split())

masu = [tuple(map(int, input().split())) for _ in range(H)]

check = set()
cnt = 0

def dfs(x,y):
    if masu[y][x] in check:
        #print(check)
        return
    check.add(masu[y][x])
    if x == W-1 and y == H-1:
        #print("flag")
        global cnt 
        cnt += 1
        return
    
    if x < W-1:
        dfs(x+1, y)
    if y < H-1:
        dfs(x, y+1)
    
    check.remove(masu[y][x])

dfs(0,0)
    
```

### 試したこと
再帰の深さの遍歴を確認しました。
returnをつけてもゴールには規定回数（３回）たどり着けているようですが、カウントが１回だけになっているようで、ここに原因があるようですが理由まではわかりませんでした。。。

```python
import sys
 
sys.setrecursionlimit(10**7)

H, W = map(int, input().split())

masu = [tuple(map(int, input().split())) for _ in range(H)]

check = set()
cnt = 0
depth = 0
def dfs(x,y, depth):
    depth += 1
    print(depth)
    global cnt 
    if masu[y][x] in check:
        #print(check)
        cnt += 0
        return
    check.add(masu[y][x])
    
    if x == W-1 and y == H-1:
        #print("flag")
        cnt += 1
        return
    
    if x < W-1:
        dfs(x+1, y, depth)
    if y < H-1:
        dfs(x, y+1, depth)
    
    check.remove(masu[y][x])

dfs(0,0,0)
    
#print(cnt)
 
```
```入力データ
3 3
3 2 2
2 1 3
1 5 4
```
```出力データ
1
2
3
3
4
4
5
2
3
4
4
5
3
4
5
```





Python 再帰関数 returnの性質

### 求める配列
Javascriptで次の例```array1```から次の```array2```を作成したい。
(実行はGoogle Apps Script)
```javascript
array1 = [[0,1,2],[],[3,4,5]];
array2 = [[0.0, null, 3.0], [0.0, null, 4.0], [0.0, null, 5.0], 
[1.0, null, 3.0], [1.0, null, 4.0], [1.0, null, 5.0], 
[2.0, null, 3.0], [2.0, null, 4.0], [2.0, null, 5.0]];
```
つまり```array2```は```array1```の重複順列を拡張したみたいな順列パターンの配列です。
具体的に言うと```array1```の二次元目の配列から一つずつ要素を抽出した配列の配列が```array2```です。
### 発生している問題

一応上記を満たす関数を作ってみましたが、処理が多すぎてOOMエラーをはいてしまいます。
以下がその関数
```javascript
const dendrogram = stem => {
  let answer =[];
  let returnedArray = [];
  if(stem.length===1){
    let lastArray = [];
    if(stem[0].length===0){
      lastArray.push([null]);
    }else{
      for(let last of stem[0]){
        lastArray.push([last]);
      }
    }
    answer=JSON.parse(JSON.stringify(lastArray));
  }else{
    returnedArray = JSON.parse(JSON.stringify(dendrogram(stem.slice(1))));
    if(stem[0].length===0){
      let returned = JSON.parse(JSON.stringify(returnedArray));
      answer = returned.map(ar=>{
        ar.unshift(null);
        return ar;
      });
    }else{
      let slisedArray = [];
      for(let n of stem[0]){
        let returned = JSON.parse(JSON.stringify(returnedArray));
        slisedArray.push(returned.map(ar=>{
          ar.unshift(n);
          return ar;
        }));
      }
      for(let sliced of slisedArray){
        for(let sl of sliced){
          answer.push(sl);
        }
      }
    }
  }
  return answer;
};
```
```arry1```の長さが小さければ処理できますが、自分が求めている```array1```がこんな感じです。
```javascript
array1 = [[0.0, 1.0, 2.0, 3.0, 4.0, 5.0], [], [], [0.0], [0.0, 
1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 
13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0], [], [0.0], [], 
[0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 
12.0, 13.0, 14.0, 15.0, 16.0, 17.0, 18.0, 19.0, 20.0], [], [0.0, 
1.0, 2.0, 3.0, 4.0, 5.0], [], [], [0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 
6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 
17.0, 18.0, 19.0, 20.0], [], [], [0.0], [0.0], [0.0, 1.0, 2.0, 
3.0, 4.0, 5.0], [0.0], [], [], [0.0], [], [], [0.0, 1.0, 2.0, 
3.0, 4.0, 5.0], [], [0.0], [], [], [0.0], [], [], [0.0, 1.0, 
2.0, 3.0, 4.0, 5.0], [0.0, 1.0, 2.0, 3.0, 4.0, 5.0], [0.0, 1.0, 
2.0, 3.0, 4.0, 5.0], [], []]
```
たったこれだけで```array2```の長さは約26億...
こちらの都合で```array1```の長さは38と決まっていますが、
二次元目の配列の長さは最大 ₃₉C₅=575,757 とふざけた数ですが、そうはならないように抑えています。
### 処理を速くしたい
プログラミング始めて1か月の人が作ったコードなのでだいぶ可読性低いと思いますが、処理を速くできる部分とか、そもそも再帰関数だから遅いとかあれば教えてください。


重複順列を拡張した配列を得る

#質問内容
二分探索の関数の作成についてです。for文を用いて二分探索の関数binaryを作成することはできたのですが、再帰呼び出しを用いてbinary関数を作成する方法の一部が分かりません。以下にプログラムと分からない箇所を示します。他の部分は合っていると思うのですが、もしお気づきの点があればご教授頂けると幸いです。


# ループを用いた二分探索のプログラム
```
#include <stdio.h>

/* プロトタイプ宣言 */
int binary(int n, int *data, int x);

/* メイン関数 */
int main()
{
   int data[8] = {1, 2, 3, 4, 5, 6, 7, 8};
   printf("%d", binary(8, data, 7));
}

/* binary関数の定義 */
int binary(int n, int *data, int x)
/* nは配列の要素数 */
/* xは検索したい数字 */
{
   int left = 0;
   int right = n - 1;

   while(left <= right)
   {
      int middle = (left + right) / 2;

      if(x == data[middle])
      {
         return middle + 1;
      }else if(x < data[middle])
      {
         right = middle - 1;
      }else
      {
         left = middle + 1;
      }
      return 0;
}
```

#再帰呼び出しを用いた二分探索のプログラム
```
#include <stdio.h>

/* プロトタイプ宣言 */
int binary(int n, int *data, int x);

/* メイン関数 */
int main()
{
   int data[8] = {1, 2, 3, 4, 5, 6, 7, 8};
   printf("%d", binary(8, data, 7));
}

/* binary関数の定義 */
int binary(int n, int *data, int x)
{
   int middle = (n - 1) / 2;

   if(x == data[middle])
   {
      return middle + 1;
   }else if(x > data[middle])
   {
      /* この部分が分かりません */
   }else
   {
      return binary(middle, data, x);
   }
   return 0;
}
   
```


#実行結果
```
7
```

再帰呼び出しを用いた二分探索(binary search)について教えてください(C言語)

予め、再帰の回数が膨大になる（10万以上とか？）と分かっている場合は、while文などで代用した方が無難なのでしょうか。
割と簡単にオーバーフローするイメージがありますが。

しかし、代用したらしたでコードが煩雑になるし、処理時間もかかってしまうのでもどかしい感じもします。