cp-9. 再帰関数

cp-9. 再帰関数 （C プログラミング入門） URL: https://www.kkaneko.jp/pro/adp/index.html 金子邦彦 1

• https://www.kkaneko.jp/pro/adp/index.html

内容 例題１．スタック 局所変数，大域変数 例題２．再帰関数による総和 2

目標 • 局所変数を使った関数を理解する • 関数の再帰呼び出しを使って，簡単な漸化式の 計算を行う 3

例題１．スタック スタックのプッシュ(push), ポップ(pop) を行う 関数を作る • • 次の２つの大域変数を使うこと 1. 配列stack 2. スタックポインタtop 4

スタックのプッシュとポップ • ポップ （出す操作） • プッシュ （入れる操作） 積み重なる ように入る 一番最後に入った データが先に出る すでに 入っていた データ すでに 入っていた データ 5

スタックとは • 入れた順に積みあがっていく push １ push 2 push 3 pop 3 1 push 4 4 2 2 2 2 1 1 1 1 6

#include <stdio.h>
int stack[100];
int top=0;
void push(int n)
{
stack[top]=n;
top++;
return;
}
int pop()
{
int n;
top--;
n = stack[top];
return n;
}

push関数

pop関数

7

スタック main 関数の例 int main() { push(1); push(2); push(3); printf( "%d\n", pop() ); push(4); printf( "%d\n", pop() ); printf( "%d\n", pop() ); printf( "%d\n", pop() ); return 0; } 8

スタック 実行結果の例 3 4 2 1 9

関数呼び出しの流れ main 関数 int main() 関数呼び出し push(1); push(2); push(3); printf( "%d\n", pop() ); push(4); printf( "%d\n", pop() ); printf( "%d\n", pop() ); printf( "%d\n", pop() ); push 関数 void push( int n ) 戻り return; pop 関数 int pop() 戻り return n; 10

配列によるスタックの実現 配列 空 空き部分の底 stack[top] スタックの頂上 stack[top-1] スタックの底 stack[0] • スタック • 十分に多くのデータを格納できる配列stackを用意． • スタックポインタ • 現在の「空き部分の底」を示す値（スタックポイ ンタ）を格納させる変数topを用意． • スタックの底は stack[0],スタックの頂上は stack[top-1] 11

配列によるスタックの実現 push １ push 2 push 3 pop 3 top 1 push 4 4 2 2 2 2 1 1 1 1 1 2 3 4 3 4 • push 時： pushの後に，topの値を１足す • pop 時： popの前に，topの値を１引く 12

局所変数 • 関数の仮引数と，関数本体内で宣言された変 数のこと • 関数の内部でだけ有効 • ほかの関数（main関数など）からは直接アクセス できない • ある関数の局所変数と，呼び出した関数中の 局所変数と，例え同じ名前であっても，別の 実体である 13

大域変数
• 関数の外側で宣言された変数のこと
例） 配列stackとスタックポインタtopは，push
関数とpop関数のいずれからも参照できる．
#include <stdio.h>
int stack[100];
int top=0;
int push(int n)
{
stack[top]=n;
top++;
return n;
}
int pop()
{
int n;
top--;
n = stack[top];
return n;
}

これが大域変数
push関数と
pop関数で
共有される

14

局所変数と大域変数 局所変数 宣言の場所 関数の仮引数 大域変数 関数の外側 または関数内 有効範囲 関数の内部だ けで有効 複数の関数で 共有される 15

スタックの使用例 • 正整数を読み込んだら，pushする． • 負整数を読み込んだら，popして，取り出された値 を表示する． • ０が読み込まれるまで上の操作を繰り返す． 16

#include <stdio.h>
#pragma warning(disable:4996)
int main()
{
int item;
top= -1;
do {
printf("Enter a number ");
scanf("%d",&item);
if (item>0) {
printf("pushed: %d\n",item);
push(item);
} else if (item<0) {
printf("popped: %d\n",pop());
}
} while (item!=0);
return 0;
}

17

課題１．スタック操作の例外処理 スタック操作のプログラムにおいて， push 関数と pop 関数を書き換えて， 次に挙げた，２つの例外事象の対処を考慮しなさい． １．スタックが空のときにポップ（pop）しない． スタックが空のときに pop 関数が呼び出されると，「Stack empty」のエラーメッセージを表示すること ２．スタックが満杯のときにプッシュ（push）しない． スタックが満杯のときに push 関数が呼びだされると， 「Stack full」のエラーメッセージを表示すること 18

課題１のヒント 空のとき 満杯のとき 配列 スタックポインタのスタックポインタの 値は 「０」 値は，「配列のサイズ」 •スタックポインタは，現在の「空き部分の底」の 位置を示す値 → 「スタック内のデータ数」に等しい 19

例題２．再帰関数による総和 • 整数Ｎから，１からＮまで総和を求める再帰関数 を作る 例） 5 → 15 if n = 1  1  n −1 i = n + i otherwise   i =1  i =1  n • 再帰関数とは，関数 f の本体にf の呼出しを含むよ うな関数のこと 20

再帰関数とは • 自分自身を呼び出すような関数のこと • 必ず終了条件が成立するように気をつけること 21

#include <stdio.h>
#pragma warning(disable:4996)
int sum(int n)
{
if (n < 1) {
return 0;
}
if (n == 1) {
return 1;
}
else {
return n+sum(n-1);
}
}
int main()
{
int n;
int s;
printf("Enter a number: ");
scanf("%d",&n);
s = sum(n);
printf("sum(%d)=%d\n",n ,s);
return 0;
}

sum関数

main関数
22

再帰関数による総和 実行結果の例 Enter a number: 2 sum(2)=3 23

関数呼び出しの流れ （main 関数で n = 2 のとき） main 関数 int main() 関数呼び出し sum(n); sum 関数 int sum( int n ) 関数呼び出しと戻 り return n + sum(n-1); sum 関数 int sum( int n ) 戻り return 1; 24

n の値の変化 （main 関数で n = 2 のとき） main 関数 int main() 関数呼び出し sum(n); sum 関数 int sum( int n ) n=2 関数呼び出しと戻 り return n + sum(n-1); sum 関数 int sum( int n ) n=1 ３を返す 戻り return 1; １を返す 25

再帰関数による総和 n == 1 No Yes return n + sum(n-1); return 1; 26

プログラム実行順 （main関数で n=2 のとき） main 関数 sum 関数 sum 関数 int main() int sum( int n ) int sum( int n ) 関数 呼び出し 関数 呼び出し printf( "Enter a number:" ); scanf( "%d", &n ); n ==1 Yes s = sum( n ); 戻り No n ==1 return n + sum(n1); return 0; 戻り Yes No return n + sum(n1); return 1; printf("sum(%d)=%d\n",n ,s); return 0; 27

データの流れ main 関数 bar関数 bar関数 int main() データ int sum( int n ) データ int sum( int n ) n 2 n 1 プログラム s = sum( n ); データ 2 プログラム n 1 プログラム 関数 関数 呼び出し ②渡された値は， 呼び出し④渡された値は， 「n」という名前で使う 「n」という名前で使う ① n の値を， return n + sum(n-1); return1; 戻り sum 関数に渡す ③ n-1 の値を， 戻り ⑤値「１」を返す ④返された値を sum 関数に渡す s に格納する 28 ⑤値「３」を返す

呼び手 return n+sum(n-1); 引数を仮引数にセットする 関 数 本 体 int sum(int n) { if (n < 1) { return 0; } if (n==1) { return 1; } else { return n+sum(n-1); } } 戻り値の受け取り 29