連結リストに限界などありますか？

Question

前提・実現したいこと

C言語で、入力した回数分のフィボナッチ数列を生成するプログラムを作成しています。
例：入力された数が5なら8、入力された数が8なら34

表示するのは上位100桁で、10,000を入力したときに正常に動くようにしたいです。

発生している問題・エラーメッセージ

基本的にはしっかり動作しているのですが、入力した数が3,618を超えると計算が止まり、プログラムが強制的に終了してしまいます。

該当のソースコード

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	struct node* prev;
	short int l;
	short int m;
	struct node* next;
}node;

void fib(node* head, node* tail, int n);

int main() {
	int n;
	node* head, * tail, * ptr, * npt;

	ptr = (node*)malloc(sizeof(node));

	ptr->prev = NULL;
	ptr->l = 1;
	ptr->m = 1;
	ptr->next = NULL;
	head = ptr;
	tail = ptr;

	scanf("%d", &n);

	fib(head, tail, n);

	ptr = head;
	while (ptr != NULL) {
		npt = ptr->next;
		free(ptr);
		ptr = npt;
	}
}

void fib(node* head, node* tail, int n) {
	node* ptr, * npt;
	int carry = 0, i = 0, tmp;

	if (n == 0) {
		ptr = head;
		while (ptr != NULL) {
			printf("%d", ptr->l);
			ptr = ptr->next;
		}
	}
	else if (n == 1) {
		ptr = head;
		while ((ptr != NULL) && (i < 100)) {
			printf("%d", ptr->m);
			ptr = ptr->next;
			i++;
		}
	}else{
		ptr = tail;
		do {
			tmp = ptr->m;
			ptr->m = ptr->l + ptr->m;

			if (10 <= ptr->m) {
				carry = 1;
			}

			if (carry == 1) {
				if (ptr->prev == NULL) {
					npt = (node*)malloc(sizeof(node));
					npt->l = 0;
					npt->m = 0;
					ptr->prev = npt;
					npt->prev = NULL;
					npt->next = ptr;
					head = npt;
				}
				ptr->m = ptr->m - 10;
			}
			ptr->l = tmp;
			ptr = ptr->prev;

			if (carry == 1) {
				ptr->l ++;
				carry = 0;
			}
		} while (ptr != NULL);

		n--;
		fib(head, tail, n);
	}

}

試したこと

連結リストに原因があるのかと思い、似たようなプログラムを配列を用いる方法で考えてみましたがそもそも配列ではしっかり動作するプログラムを書けませんでした。

連結リストにこだわっているわけではなく、入力した回数分のフィボナッチ数列を生成できればOKです。

どなたかプログラムが停止する理由、また代案などあればご教示願います。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

原因は、fibの再帰呼び出しです。

関数の引数やローカル変数を保存するためのスタック領域は、環境により異なりますが、数MBしかありません。
そのため、再帰呼び出しを大量に繰り返すと、スタック領域を使いつくして落ちます。

再帰をループに書き換えたところ、私の環境では10,000でも動作するようになりました。

Comments

[dgtack25]

連結リストではなく、再帰に限界があったのですね。ありがとうございます。
ちなみにループへはどのように書き換えればよいのでしょうか？

[actorbug]

ざっくり手順を説明すると以下になります。
1. 関数内部全体をfor(;;){...}で囲む
2. if文の分岐で再帰呼び出ししていない箇所については、明示的にreturnで抜けるようにする
3. 再帰呼び出ししている箇所については、再帰呼び出しの実引数を仮引数に代入する処理に置き換える

検索してもあまり情報が見つかりませんでしたが、以下のページなど参考になるかもしれません。

2019年度「プログラミング言語」配布資料 (6) 末尾再帰関数から繰り返し処理へ
http://www.fos.kuis.kyoto-u.ac.jp/~igarashi/class/pl/06-rec-iter.html#trans-tail-recursion

[dgtack25]

丁寧な説明ありがとうございました。ループに書き換えたところ上手く動作しました。

Answer 2

まず、

                npt = (node*)malloc(sizeof(node));

mallocしたときはNULLチェックしましょう。