C++のクラスで
n!=n(n-1)(n-2)...1
n!を求めるprogramを作らなくてはならないのですが
再帰を使わずに、関数factorial(n)を使わないといけません。
ちんぷんかんぷんです。
for(counterとcounter--を使った)物しか思いうかびません。
関数factorial(n)を使うというのはnに戻るつまり再帰というふうには
ならないのですか?
関数と再帰の意味を漠然としかわかっていないのですが。
よろしくお願いします。

このQ&Aに関連する最新のQ&A

A 回答 (2件)

C++は知りませんがC言語の知識で。


factorial関数を使うなら簡単ですね。k=factorial(n)
これでNの階乗がkに入るはずです。

再帰処理は、関数の中でやっているかもしれません。
再帰処理を簡単に説明すると、factorialの中でfactorialを使うというような奇妙な組み方です。
もう少しわかりやすく言うと、10!を計算するように言われたとき10を横にどけて9!を計算するように自分自身に命令しなおします。これを繰り返していくと最後は1!=1を計算することになります。
後は逆向きに戻りながら掛け算をしていき、最後に10!が求まります。

ところで、factorialは自分で組むのですか?
    • good
    • 0

まるで、なぞなぞのようです。


階乗(factorial)のプログラムを作るのならば、factorial(n)を使わないといけないという意味がわからないし、クラスの設計力を試されているのなら、あえて再帰という言葉を使う意図がわかりません。
「何を作るのか」という事をはっきりさせた方がいいですよ。

関数の説明は省略しますが、再帰というのは、以下のように、関数が自分自身を呼び出している状態をさします。

int factorial(int n)
{
if (n > 2) n *= factorial(n - 1);
return n;
}
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aと関連する良く見られている質問

Q再帰関数squares()で完全平方根を帰す

整数のint nを受け取り、 最初からn個の完全平方根を大きい順で返す再帰関数を教えてください。
完全平方根 1(1*1)、4(2*2)、9(3*3)などです。

Aベストアンサー

「完全平方数」の間違いではないかと。

#include <stdio.h>

void squares(int n)
{
 if (n < 1) return;

 printf("%d\n", n*n);
 squares(n-1);
}

int main()
{
 squares(10);

 return 0;
}

# 課題じゃなきゃループを使うと思う。

Q再帰関数を使うとき、ソフトウェアスタックはハードウェアスタックと比べてどれくらい遅い?

再帰を使って関数を書こうと思うのですが、再帰する回数が不明なので、スタックオーバーフローを避けるためソフトウェアスタックを使おうと思っている者です。

ソフトウェアスタックはどれくらい遅いのでしょうか?
どう実装すれば速度が改善されるのでしょうか?

Aベストアンサー

ハードウェアスタックって言うのが、スタックポインタ(レジスタ)を使用した物で、ソフトウェアスタックって言うのが、ハードウェアスタックを使用しない擬似スタック操作だとすると、その遅さは?

通常のスタック操作は、アセンブリ言語で1命令になります。
擬似的にソフトウェアでスタック操作を行うとなると、アセンブリレベルで何命令必要か?と言うことになります。
C言語で数命令でもアセンブリレベルだと数~数十命令になりますので、何十倍も遅くなると思います。

call命令等のスタック操作をソフトウェアで実現することはまず無意味なので、おそらくオート変数のみを別配列等で構築し、それを操作する?と言った意味ですか?

そうすると、それ程遅くはならないでしょう。
ポインタを上手く使えば、Cコンパイラの最適化処理が効率よくコンパイルしてくれると思います。
実装方法としては、必要な変数を構造体等にまとめ、その配列を構築し、それらをポインタで管理すればよいと思います。
オート変数の場合は、スタック上に構築した後、スコープを外れる時に破棄する無駄な動きが発生しますが、上記のようにすると、構築・破棄と言った無駄な処理がなくなるので、オート変数を使用した再帰より速くなる可能性が十分あります。
そしてオーバーフローも簡単に管理できますね。

ハードウェアスタックって言うのが、スタックポインタ(レジスタ)を使用した物で、ソフトウェアスタックって言うのが、ハードウェアスタックを使用しない擬似スタック操作だとすると、その遅さは?

通常のスタック操作は、アセンブリ言語で1命令になります。
擬似的にソフトウェアでスタック操作を行うとなると、アセンブリレベルで何命令必要か?と言うことになります。
C言語で数命令でもアセンブリレベルだと数~数十命令になりますので、何十倍も遅くなると思います。

call命令等のスタック操作をソフ...続きを読む

Q関数の再帰とは??[C言語]

関数の再帰とは何ですか??
教えてください。

Aベストアンサー

以下のサンプルのように、関数内部から自分自身を呼ぶことです。

void func() {
  func();
}

この関数は実際の仕事は何もしていないので存在価値がありませんし、
関数コールが無限に続く構造ですので、すぐにリソースを食い尽くして異常終了してしまうでしょう。

何かしら仕事をさせるなら、例えば以下のような関数になります。
引数で指定した値までの正の整数を昇順に表示する関数です。
再帰呼び出しを行う前に表示するよう変更すれば、表示は降順になります。

void func(int i) {
  if (i > 0) {
    func(i-1); /* 再帰呼び出し */
    printf("%d, ", i);
  }
}

Q再帰処理を非再帰処理に書き換える場合

TreeViewなど階層数・要素数が動的に変化し
それらすべての要素に対して一括処理をするといった
本質的に、真に再帰的な操作をしなければならないような場合なのですが

状況説明のため少ないメンバに絞ると
こんなノードの抽象クラスがあるとします

namespace TreeView { namespace Node { class Super; }}
class MemoryMap;

class TreeView::Node::Super {

protected:

typedef Super* PTR;
PTR next, child;

Super();
virtual ~Super();
virtual Void Save( MemoryMap* ) const = 0;

public:

static Void Release( PTR* pp );
template <class T> static Void Release( T** pp ){ Release( (PTR*)pp ); }

};


んで

using TreeView::Node::Super;

Super::Super() : next(NULL), child(NULL){}
Super::~Super(){}

こんな感じにしといて、任意に追加、挿入しときますと

その後一括解放のためのReleaseの本体は

Void Super::Release( PTR* pp ){

for ( PTR p; p = *pp; ){
if ( p->child ) Release( &p->child );
*pp = p->next;
delete p;
}

}

こんな感じで、再帰を使えば結構簡単に書けると思うのですが


・・・利用法から考えてよっぽどないとは思うのですが
やはりそこは一応
スタックオーバーフローの危険性をコードサイドから積極的に
ほぼ回避しておくべきと考えると

階層数の上限を設けておいて
最低、追加・挿入時には、それをチェックする

というのが良いかと思うのですが

仮に別のアプローチで
こういった類の再帰(もっと複雑な場合のが多いかも)を非再帰関数に直すには
やっぱり


・goto文
・自分でヒープ上などに作る疑似スタック
・そのスタックに、gotoのジャンプ位置を保存できるenumとかの定数フラグ


などを使用せざるを得ない
って感じになってくるんでしょうかね?

TreeViewなど階層数・要素数が動的に変化し
それらすべての要素に対して一括処理をするといった
本質的に、真に再帰的な操作をしなければならないような場合なのですが

状況説明のため少ないメンバに絞ると
こんなノードの抽象クラスがあるとします

namespace TreeView { namespace Node { class Super; }}
class MemoryMap;

class TreeView::Node::Super {

protected:

typedef Super* PTR;
PTR next, child;

Super();
virtual ~Super();
virtual Void Save( MemoryMap* ) const = 0;

public:

static Voi...続きを読む

Aベストアンサー

別にgotoは使わなくてもいいんじゃないですか?
PTRをスタックするだけで。
ループの繰り返し

void Super::Release( PTR* pp ){
std::stack<PTR> sp; // スタックの準備
sp.push(*pp) ; // 次に処理したいノードをスタックに積む
// 関数での引数に相当。

while ( ! sp.empty() ){ // スタックが空→終了
// トップの内容を見る。スタックは変化しない
// 関数で引数の受け取りに相当
PTR p = sp.top() ;

if( p == NULL ) {
// 関数でのreturnに相当
sp.pop() ; // topは処理済みになるのでスタックから削除
continue ; // 次へ
}

if ( p->child ) { // 子があったら、
sp.push(p->child) ;// 子をスタックへ積んで
continue ; // 次へ:再帰呼び出しに相当
}

sp.push(p->next); // 次の候補であるp->nextをスタックに積む

*pp = p->next;
delete p;

sp.pop() ; // topは処理済みになるのでスタックから削除

}
}

別にgotoは使わなくてもいいんじゃないですか?
PTRをスタックするだけで。
ループの繰り返し

void Super::Release( PTR* pp ){
std::stack<PTR> sp; // スタックの準備
sp.push(*pp) ; // 次に処理したいノードをスタックに積む
// 関数での引数に相当。

while ( ! sp.empty() ){ // スタックが空→終了
// トップの内容を見る。スタックは変化しない
// 関数で引数の受け取りに相当
PTR p = sp.top() ;

if( p == NULL ) {
// 関数でのreturnに相当
sp.pop() ; // topは処理済みになるのでスタックから削除
co...続きを読む

Q素数 再帰関数

メイン
#include<stdio.h>
extern void count_primes(void);
extern void print_primes(void);
int max;
int count;
int primes[1000]
int main(void)
{
printf("Uper limit: ");
scanf("%d",&max);
count_primes();
print_primes();
}
素数を求める(関数呼び出し)
extern int nextprime(int n);
extern int max;
extern int count;
extern int primes[];
void count_primes(void)
{
int i;
count=0;
for(i=2;i<=max;i=nextprime(i)){
primes[count++]=i;
}
リカーバシブ(次の素数)
int nextprime[int n]
{
int i;
for(;;){
n++;
for(i=2;i*i<=n;i=nextprime(i)){
if(n%i==0)
break;
}
if(i*i>n)
break;
}
return n;
}
素数プリント
#include<stdio.h>
extern int count;
extern int primes[];
void print_primes(void)
{
int i
for(i=0;i<count;i++){
if((i>0)&&(i%10==0)
printf("\n");
printf(" %6d",primes[i]);
}
printf("\n素数の数 %d\n",count);
}
これら4つのモジュールで素数 nが求められますがアルゴリズム理解できません。この2つの関数のアルゴリズムについて、ご教授ください。め

メイン
#include<stdio.h>
extern void count_primes(void);
extern void print_primes(void);
int max;
int count;
int primes[1000]
int main(void)
{
printf("Uper limit: ");
scanf("%d",&max);
count_primes();
print_primes();
}
素数を求める(関数呼び出し)
extern int nextprime(int n);
extern int max;
extern int count;
extern int primes[];
void count_primes(void)
{
int i;
count=0;
for(i=2;i<=max;i=nextprime(i)){
primes[coun...続きを読む

Aベストアンサー

int nextprime(int n) {
 int i;
 for(;;){
  n++; /* 次の素数候補 */
  /* i: 2から始めて√nを超えない範囲で */
  for(i=2;i*i<=n;i=nextprime(i)){
   /* nがiで割り切れたならnは素数でない */
   if(n%i==0)
   break;
  }
  /* 上のループを抜けたとき i*i > n であったなら
   * nを割り切るiがなかった、すなわちnは素数である。
   * 素数が見つかったので無限ループを抜ける */
  if(i*i>n)
   break;
 }
 return n;
}


このカテゴリの人気Q&Aランキング

おすすめ情報