常連

初歩的な質問で恐縮ですが、ご教示下さい。

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」の再帰的について

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

再帰を用いる際の注意点

#質問内容
二分探索の関数の作成についてです。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言語)

Python3.7の質問です。

ある関数の内部でそれ自身を呼び出す処理を行うときに、「今何回目の呼び出し中か？」を参照できるようにしたいです。
例えば下のコードの場合、func()が何重に呼ばれた段階かによって「処理」と書かれた部分らの動作を変化させる、といった状況です。
```Python3
def func():
    if 条件式:
        処理
        func()
    else:
        処理
        return
```

それで、↓の様に関数定義の外にグローバル変数を置いてそれを処理回数のカウンターとして使って……というのを考えました。（使うときは```wrap()```を呼ぶ）
```Python3
def wrap():
    global count
    count = 0
    func()

def func():
    if 条件式:
        処理A(countの値に応じて)
        count += 1
        func()
    else:
        処理B(countの値に応じて)
        return
```
これ↑なら処理が複雑になっても対応できます。↓
```Python3
def wrap():
    count = 0
    func()

def func_with_count():
    global count
    count += 1
    func()
    count -= 1

def func():
    global count
    if 条件式1:
        処理A-1
        func_with_count()
        処理A-2
        func_with_count()
    else:
        処理B
        return
```
しかし長ったらしくて後から読み返しにくいものになってしまいました。

何か簡単な書き方はないでしょうか。（関数をいくつ呼び出しているかを取得する特殊変数とかあったりしないでしょうか）


最初の例だとwhileを使えばすぐ書ける気もしますが、if分岐がelifだらけの場合等ではうまく書けませんでした。


なんだか変な質問文になってしまいましたがどなたか回答お願いします。

Python3: 再帰的な関数内で「今何回再帰しているか」の回数を取得したい

### 前提・実現したいこと

pythonのクイックソートの関数を定義し、思うように動作できたのですが、比較回数と交換回数をカウントしようとあれこれやっているのですが、うまく動作せず試行錯誤しています。

### 発生している問題・エラーメッセージ
comp は比較回数、sort は交換回数として、実行すると以下のように途中から数字が乱れていきます。

-追記-
比較回数が正しいカウント数にならないです。
どこにインクリメント式を挿入していればいいのでしょうか？
クイックソートにおける比較箇所がいまいちわかりません。
```
comp = 1
comp = 2
comp = 3
comp = 4
comp = 5
comp = 6
comp = 7
sort = 1
comp = 8
comp = 9
comp = 10
comp = 11
comp = 12
sort = 2
sort = 3
comp = 13
comp = 14
comp = 15
sort = 4
comp = 16
sort = 5
sort = 6
sort = 5
sort = 2
```

### 該当のソースコード
カウントする処理を入れる前のクイックソートのソース
```python
def quick_sort(arry):

    n = len(arry)
    if n <= 1:
        return arry

    center = arry[0]
    right=[]
    left=[]

    for i in range(1,n):
        if arry[i][2] >= center[2]:
            left.append(arry[i])
        else:
            right.append(arry[i])

    r = quick_sort(right)
    l = quick_sort(left)

    return l+[center]+r
```
カウント処理を加えてみたソース
```python
def quick_sort(self, data, comp_count, sort_count):

    n = len(data)
    if n <= 1:
        return data

    center = data[0]
    right=[]
    left=[]

    for i in range(1,n):
        if data[i][2] >= center[2]:
            left.append(data[i])
        else:
            right.append(data[i])
        comp_count += 1
        print("comp = %s" %comp_count)

    sort_count += 1
    print("sort = %s" %sort_count)
    r = quick_sort(self, right, comp_count, sort_count)
    sort_count += 1
    print("sort = %s" %sort_count)
    l = quick_sort(self, left, comp_count, sort_count)

    self.comp_count = comp_count
    self.sort_count = sort_count

    return l+[center]+r
```

### 試したこと

再帰する際におかしくなっていると推測できたので、カウントの位置を変えたり引数を考えてみたりしましたが、これといった解決法が思いつきません。
カウントする際の変数は、データ構造？を使ってますが特にこだわりはありません。

### 補足情報（FW/ツールのバージョンなど）

python3.8.2のOS X Mojaveです。

pythonクイックソートの比較回数と交換回数について

### 前提・実現したいこと


[Atcoder Typical Contest 001 A 深さ優先探索](https://atcoder.jp/contests/atc001/tasks/dfs_a)について、
（１）のコードはPython (3.8.2)、PyPy3 (7.3.0)のどちらで提出してもACになりますが、（２）のコードをPyPy3 (7.3.0)で提出すると１、２個のテストケースでTLE、MLEになります。
違いはdfs関数内のif文です。（（２）のコードをご覧になってください）




### (1)

```python
import sys
sys.setrecursionlimit(500*500)

h,w = map(int,input().split())
maze = [list(input()) for _ in range(h)]

visited = [[False]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j] == "s":
            sx = i
            sy = j
        elif maze[i][j] == "g":
            gx = i
            gy = j


def dfs(x,y):
    if x < 0 or x >= h or y < 0 or y >= w: return
    if  maze[x][y] == "#" or visited[x][y]: return
    visited[x][y] = True
    dfs(x-1,y)
    dfs(x+1,y)
    dfs(x,y+1)
    dfs(x,y-1)

    
dfs(sx,sy)

if visited[gx][gy]:
    print("Yes")
else:
    print("No")
    

```
###(2)
```python
import sys
sys.setrecursionlimit(500*500)

h,w = map(int,input().split())
maze = [list(input()) for _ in range(h)]

visited = [[False]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j] == "s":
            sx = i
            sy = j
        elif maze[i][j] == "g":
            gx = i
            gy = j


def dfs(x,y):
    if x < 0 or x >= h or y < 0 or y >= w: return
    if visited[x][y] or maze[x][y] == "#" : return # orの前後の値を入れ替えた
    visited[x][y] = True
    dfs(x-1,y)
    dfs(x+1,y)
    dfs(x,y+1)
    dfs(x,y-1)

    
dfs(sx,sy)

if visited[gx][gy]:
    print("Yes")
else:
    print("No")
    

```

### 試したこと

visited[x][y]を先に判定していることが原因だと思うのですが、それでなぜTLE,MLEになるのかわかりません。

【Atcoder】PythonだとACになるがPyPyだとTLEになる

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


### 前提

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の端末


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

ハノイの塔を再帰で実装するプログラムを教わりましたが、なぜ、これだけのコードでハノイの塔が解けるのかがわかりません。
プログラムの動く道筋をひとつひとつ細かく教えてほしいです。
このコードがどうやって円盤の大きさや位置を考慮して円盤を動かしてるのかが知りたいです。プログラムの動きを言葉で表してほしいです。
```C
#include<stdio.h>

void Hanoi(int n,char *from,char *work,char *dest)
{
  if(n>=2) Hanoi(n-1,from,dest,work);

  printf("%d を %s から %s へ\n",n,from,dest);

  if(n>=2) Hanoi(n-1,work,from,dest);
}

int main(void)
{
  Hanoi(4,"A","B","C");

  return 0;
}
```