コラッツ問題における再帰関数のカウント数が表示されない。

Question

質問内容

初歩的な質問で非常に申し訳ないです。c言語についての質問です。コラッツ問題について関数を呼び出した回数をカウントするプログラムを作りたいのですが、うまくいきません。条件として、while文やfor文などのループ関数は使わないことが必須です。自分は再帰関数でプログラムを組みました。ソースコードは以下です。

＃include<stdio.h>
int h(int n){
int count=0;
if(n==1){
count++;
return count;
}else{
if(n%2==0){
count++;
n==n%2;
h(n);
}else{
count++;
n==3*n+1;
h(n);
}
}
}
int main(void){
int n=2020,count;
count=h(n);
printf("%d",count);
return 0;
}

結果

関数自体は動くのですが、結果が表示されません。これは、何が原因でしょうか。分かる方いたら、回答をよろしくお願いします。

Answer 1

#include <stdio.h>

int h(int n, int c){
  if ( n == 1 ) {
    return c;
  };
  
  if ( n % 2 == 0 ) {
    return h(n/2, c+1);
  } else {
    return h(n*3+1, c+1);
  }
}

int main(void){
  int n = 3;
  int count = h(n, 0);
  printf("%d",count);
  return 0;
}

nによってはとてつもなく大きな値となるので再帰で解くのはオススメしかねるんですけども...

Comments

[fana]

「末尾再帰最適化」とかいうやつですか？

[episteme]

「末尾再帰はループで置き換え可能」ってやつっすね。

Answer 2

1. まず，コードがわりと間違っています．

h()内でh()をコールするとき，全く同じnの値を引数に渡しているのでスタックを食いつぶすまで再帰します．
n==n%2;とかでは，nの値は更新されないからです．（さらに，扱う問題的に，n%2というのも間違っているように思われる）

1. 関数h()内でreturnが書かれているのはif(n==1){}のブロック内だけです．

なので，mainからhに1でない値を渡したとき戻り値が何になるのかは謎です．
（戻り値を返すべき関数がreturnが無いパスから抜けたときに何が起こるのか？　その振る舞いに規定が存在するのかどうかを私は知りませんが，いずれにしろそれが所望の処理ではないであろう，と思います．）

1. やりたいことの意味的には，変数countはおそらくstatic変数にすべきなのではないかと思います．

…といった感じで，全体的にぐちゃぐちゃな状態に見えます．
関数h()が呼ばれる度に引数nの値をprintf()か何かで表示させてみる等して，現状の振る舞いがどうなっているのか（何が起こっているのか）を確認してみることから始めると良いのではないかと思います．

---

[追記]
｛関数が呼ばれた回数をカウントする，再帰でコラッツ問題｝と，やりたいことが２つ混在している状況です．
これを同時に考えると混乱するようであれば，１個ずつ順に解決していけば考えやすいのではないでしょうか．

関数が呼ばれた回数をカウントしたいならば，まずはそれだけを素直に書けば以下のようになるでしょう．

int h( int n )
{
  static int count = 0;  //staticでカウンタを用意．
  ++count;  //とくかく呼ばれたらカウンタをインクリメントする．

  //(処理)

  return count;  //現在のカウンタ値を返す
}

なので，あとは「コラッツ問題で再帰がどうの」という処理内容を，上記コード内の//(処理)の部分に追加すればよいでしょう．
「コラッツ問題」でググってwikipediaで見た内容を本当に素直にそのまま書けば，こんな程度↓の内容になるんじゃないでしょうか？

if( n != 1 )  //1じゃないとき
{
  if(n%2==0){  h(n/2);  }  //２の倍数なら２で割る
  else {  h(n*3+1);  }  //そうじゃないなら３倍して1足す
}

Comments

[fana]

質問文を書く際に手動でコードを写す等した結果として記述をミスっているだけなのか，
それとも本当に現状のコードがこの状態なのか，
こちらには判断は付きませんが，
いずれにしろ，所望の動作をしていないのであれば，各所にprintfを仕込むとかデバッガを使うなどして，現状の動きを追ってみるべきでしょう．そうすればすぐに「ん？」と気付けるであろうと想像します．

[katkey]

丁寧な回答ありがとうございます。いろいろ試してみようと思います。