pythonの再帰呼び出しの使い方に関して

Question

大学のプログラミングの講義で、pythonで線形リストを扱っています。

class Cell:
info : Any
next : Any
このように、info でリストの要素を、next で次のセルを指すポインタを表現していて、
例えば[-27,823,54]からなる線形リストを

Cell(-27, Cell(823, Cell(54, None)))

のように構成しています。
次に数学の話ですが、以下はすべて整数範囲の話です。
あるn次元多項式f(x)について、
f(x)=a_0+a_1 x+a_2 x^2+⋯+a_(n-1) x^(n-1)+a_n x^n
の係数が、実装した線形リストの要素として表されています。
Cell(a_0, Cell(a_1, Cell(a_2, Cell( ...Cell(a_n-1, Cell(a_n, None)...))))
ということです。

話がややこしくて申し訳ないのですが、
ここで考えたいのが、この多項式f(x)についてx=bのときの解についてです。
これを求めるプログラムを、再帰関数で実装したいのです。

ホーナー法という多項式の計算法を、再帰性を利用して表現したく、
a_0 + b*(a_1 +b*(a_2 + ...+b*(a_n-1 + b*a_n))...)という数式を考えていて、
カッコで囲まれた部分に再帰性を使えないかと思っています。
いろいろ試しているのですが、うまくいかないです。

おそらく、関数の引数のリストのポインタが、Cell丸ごとではなく要素を直接指し示す、
もしくは要素だけ再帰呼び出しをかける、などできたらうまくいくのではないか、と素人ながら考えているのですが、何かアイデアをいただけたらと思って投稿させていただきました。

追記
TypeError が出たのですが
これは、「関数の呼び出し部分が整数値でない」という意味であっていますか？

少し調べましたがエラーメッセージを正しく解釈できているかわかりません。
また、これに対する解決案も何かありましたらよろしくお願いします。

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

Traceback (most recent call last):

File "<stdin>", line 1, in <module>
File "main.py", line 28, in eval_poly
return a * eval_poly(p.next, a) + p.info
File "main.py", line 28, in eval_poly
return a * eval_poly(p.next, a) + p.info
File "main.py", line 28, in eval_poly
return a * eval_poly(p.next, a) + p.info
TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'

該当のソースコード

def eval_poly(p,a):
   if p is None:
     return None
   else:  
     return a * eval_poly(p.next, a) + p.info
     

試したこと

def eval_poly(p,b):
    return eval_poly(p.next, b) * b + p.info

というコードでは、
AttributeError: 'NoneType' object has no attribute 'next'
のメッセージが出ました。これは再帰呼び出しの停止条件がなかったためだと
ご指摘をいただきました。

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

real.it でソースを書いています。

Answer 1

def eval_poly(p,a):
   if p is None:
     return None
   else:  
     return a * eval_poly(p.next, a) + p.info

これだとp.next=Noneの場合、上の最後の式は以下のような計算をすることになります。

     return a * None + p.info

なので、TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'と言われています。以下みたいな感じでちゃんと終了条件を考慮しないといけません。

def eval_poly(p,a):
   if p is None:
     return None
　　elif p.next is None:
     return p.info  
   else:  
     return a * eval_poly(p.next, a) + p.info

Comments

[studioperon]

教えていただいた通りのプログラムできちんと動きました。
他の方々からもご指摘していただいたように、きちんと終了条件を考える必要がありました。

エラーの内容と原因まで詳しく教えていただき勉強になりました。ありがとうございました。

Answer 2

再帰関数を作るには、
・停止の条件
・次の処理の呼び出し
の2つが必要です。

def eval_poly(p,b):
    return eval_poly(p.next, b) * b + p.info

この関数には、次の処理の呼び出しはありますが、停止条件がありません。
なので、最後のセル 「Cell(a_n, None)」に到達しているのに、Noneのnextを 参照しようとしてエラになっています。

nextがNullだったらxxxを返すという処理を追加すれば再帰処理そのものは動くようになると思いますよ。

Answer 3

アルゴリズムを正しく把握できているかは自信がありませんが、とりあえず再帰を書くのであれば終了条件は何らかの形で決める必要があります。

リストの末尾までたどってpがNoneになったときの処理ですね。0を返すことにするor次でNoneになるという判定をしてそれ以上再帰しないようにする、のどちらかで、再帰を止めないといけません。