cp-9. 再帰関数

>100 Views

February 21, 22

スライド概要

(C プログラミング入門)
URL: https://www.kkaneko.jp/cc/adp/index.html

profile-image

金子邦彦(かねこくにひこ) 福山大学・工学部・教授 ホームページ: https://www.kkaneko.jp/index.html 金子邦彦 YouTube チャンネル: https://youtube.com/user/kunihikokaneko

シェア

埋め込む »CMSなどでJSが使えない場合

各ページのテキスト
1.

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

2.

内容 例題1.スタック 局所変数,大域変数 例題2.再帰関数による総和 2

3.

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

4.

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

5.

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

6.

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

7.
[beta]
#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

8.

スタック 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

9.

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

10.

関数呼び出しの流れ 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

11.

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

12.

配列によるスタックの実現 push 1 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の値を1足す • pop 時: popの前に,topの値を1引く 12

13.

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

14.
[beta]
大域変数
• 関数の外側で宣言された変数のこと
例) 配列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.

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

16.

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

17.
[beta]
#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

18.

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

19.

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

20.

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

21.

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

22.
[beta]
#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

23.

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

24.

関数呼び出しの流れ (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

25.

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 3を返す 戻り return 1; 1を返す 25

26.

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

27.

プログラム実行順 (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

28.

データの流れ 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 の値を, 戻り ⑤値「1」を返す ④返された値を sum 関数に渡す s に格納する 28 ⑤値「3」を返す

29.

呼び手 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