常連

ハノイの塔を再帰で実装するプログラムを教わりましたが、なぜ、これだけのコードでハノイの塔が解けるのかがわかりません。
プログラムの動く道筋をひとつひとつ細かく教えてほしいです。
このコードがどうやって円盤の大きさや位置を考慮して円盤を動かしてるのかが知りたいです。プログラムの動きを言葉で表してほしいです。
```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;
}
```

ハノイの塔のプログラムがなぜ動くのかがわからない

### 前提
フィボナッチ数列を用いて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文、再帰処理に関する質問(フィボナッチ数列)

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

再帰を用いる際の注意点

C言語で再帰呼び出し使ってプログラムをつくりたいのですが、
難解でどうすればいいのか四苦八苦しています。
どなたかアドバイスを頂けないでしょうか？


### 問題


> 200円を1円、5円、10円、50円、100円の5種類の硬貨を使って、何通りの支払い方法があるかを求めるプログラムを再帰呼び出しを使って作る。関数change(int n, int k)を定義（n 円をk 円以下の硬貨で支払う支払い方の数を返す関数）し、main()関数では、支払う金額を1円から200円まで1円きざみで繰り返して「1円 = 1通り」、、「200円 = ???通り」のように、200行の出力を得られるようにする。

現状として1円から200円まで1円きざみで繰り返すことはできたのですが、
「1円 = 1通り」、、「200円 = ???通り」と表す時に、下記のようになってしまいます。
1円＝1通りのように横並びに書くにはどうすればいいのでしょうか。
```ここに言語を入力
1円=
2円=
3円=
4円=
.
.
.
196円=
197円=
198円=
199円=
200円=
0通り
```
また、何通りか表す時に0になってしまうのですが、
どう組み合わせを変更したら良いものか全く手が出ず困っています。

サンプルプログラムしかりアドバイスしかり、
ご助力願えないでしょうか。
どうかよろしくお願いします。

### 現状
```c
#include <stdio.h>
#include <stdlib.h>

// カウンタ変数
int i, count;
//支払い方法の数を数える関数(n:200円をk:100円以下の硬貨で)
int change(int n, int k){

    int count;
    for(int i = 1; i <= 200; i++){
      count = i;
      printf("%d円=\n",count);
    }

  //change(n, 1) は，1円玉だけしか使えないので1通り
  if (count == 1) {
    return 1;
  } else if(count == 5) { //change(n, 5) は，change(n, 1) + change(n −5, 5)
    return change(n, 1) + change(n - 5, 5);
  } else if(count == 10) { //change(n, 10) は，change(n, 5)+change(n−10, 10)
    return change(n, 5)+change(n - 10, 10);
  } else if(count == 50) { //change(n, 50) は，change(n, 10)+change(n−50, 50)
    return change(n, 10)+change(n - 50, 50);
  } else if(count == 100) { //change(n, 100) は，change(n, 50)+change(n−100, 100)
    return change(n, 50)+change(n - 100, 100);
  } else{
    return 0;
    }
  }


int main(){
  int way;
  way = change(200, 100);
  printf("%d通り\n", way);
  exit(0);
}
```

### 試したこと

横に並べようと思い、以下のようにしてみたのですが、上手くいきませんでした。
```c
#include <stdio.h>
#include <stdlib.h>

//支払い方法の数を数える関数(n:200円をk:100円以下の硬貨で)
int change(int n, int k){

  //change(n, 1) は，1円玉だけしか使えないので1通り
  if (k == 1) {
    return 1;
  } else if(k == 5) { //change(n, 5) は，change(n, 1) + change(n −5, 5)
    return change(n, 1) + change(n - 5, 5);
  } else if(k == 10) { //change(n, 10) は，change(n, 5)+change(n−10, 10)
    return change(n, 5)+change(n - 10, 10);
  } else if(k == 50) { //change(n, 50) は，change(n, 10)+change(n−50, 50)
    return change(n, 10)+change(n - 50, 50);
  } else if(k == 100) { //change(n, 100) は，change(n, 50)+change(n−100, 100)
    return change(n, 50)+change(n - 100, 100);
  } else{
    return 0;
    }
  }


int main(){
  int i, count, way;
  way = change(200, 100);
  for(int i = 1; i <= 200; i++){
    count = i;
    printf("%s円=\n","%d通り\n", count, way);
  }
  exit(0);
}
```
上記のエラー
```c
test6.c:29:37: warning: data argument not used by format string [-Wformat-extra-args]
    printf("%s円=\n","%d通り\n", count, way);
           ~~~~~~~~~             ^
1 warning generated.
```

【C言語 再帰呼び出し】 表示方法と硬貨の支払いについて

初歩的な質問で恐縮ですが、ご教示下さい。

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クイーン問題の再帰関数による解法（アルゴリズム）をわかりやすく解説して下さい。

### 実現したいこと
以下のソースコードの「alg関数」がどのようなアルゴリズムとなっているのか、できればわかりやすく説明していただくことはできますか？
特に、alg関数の「while (j < queen && i != tab[j] && abs(tab[j] - i) != queen - j)」以降の部分が何をしているのか理解することができておりません。
何卒宜しくお願い致します。

### 試したこと
以下のソースコードを実行すると以下の結果が出力されます。

0257948136
0258693147
0258693174
0286931475
0358297146
(中略)
9713068524
9741306825
9741306852
9742051863

10×10の盤のどの行にクイーンが配置されているかの結果が出力されていることは理解できています。
例えば最初の出力の0257948136は、0列目の0行目の位置、1列目の2行目の位置、2列目の5行目の位置、3列目7行目の位置....にクイーンが置かれていることを示している。

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

```C言語
#include <unistd.h>

void	outputchar(char c)
{
	write(1, &c, 1);
}

int	abs(int n)
{
	if (n > 0)
		return (n);
	else
		return (n * -1);
}

void	alg(char *tab, int queen, int *t_out)
{
	int	i;
	int	j;

	if (queen == 10)
	{
		queen = 0;
		while (queen < 10)
			outputchar(tab[queen++] + 48);
		outputchar('\n');
		(*t_out)++;
		return ;
	}
	i = -1;
	while (++i < 10)
	{
		j = 0;
		while (j < queen && i != tab[j] && abs(tab[j] - i) != queen - j)
			j++;
		if (j >= queen)
		{
			tab[queen] = i;
			alg(tab, queen + 1, t_out);
		}
	}
}

int	ten_queens_puzzle(void)
{
	char	arr[10];
	int		que;
	int		total_out;

	que = 0;
	total_out = 0;
	alg(arr, que, &total_out);
	return (total_out);
}

int	main(void)
{
	ten_queens_puzzle();
	return (0);
}

```

10クイーン(Nクイーン)問題(C言語)の再帰関数による解法(アルゴリズム)について解説して下さい(コード提出済み)

#質問内容
二分探索の関数の作成についてです。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だらけの場合等ではうまく書けませんでした。


なんだか変な質問文になってしまいましたがどなたか回答お願いします。