このパズルを再帰的にプログラミングする方法は？

Question

私は頭の中で頭脳を解決しましたが、私は再帰的な定義に翻訳するのが難しいです。ブレーンジーザーは、壊れた体重の問題（https://mathlesstraveled.com/2010/05/01/the-broken-weight-problem/）です：

落札の結果、4ポンドの測定重量がありました。その後ピースを秤量すると、各ピースの重量は全ポンドであり、4つのピースを使用して1〜40ポンドの積載重量を計量することができることが判明した。どのくらいの重量のものだったの？

だから、答えは、前の項の二倍の和として一般化することができる（1,3,9,27）+ 1

私は再帰的に返すようにPythonの関数を記述しようとしていますシーケンスのn番目の項と私はまだ再帰をうまく行っていないので、それの困難な時間を持っている。私は一種の

....私も実行中の合計を返すために持っていることを考え出しこれは、これまでのところ、私の思考プロセスの不完全なコードです：

def x(n): 
    if n == 1: 
    sum = term = 1 
     return (sum, term) 
    else: 
    term = (sum*2)+1 
    sum = sum+term 
    return (sum,term) 

このコードが壊れていると、「発生しますローカル変数 'sum'が代入前に参照されています。どうすればこれについて最善の考えをすることができますか？

Answer 1

私は、これはあなたが探しているコードであると考えている：

def _x(n): 
    if n <= 1: 
     return (1,1) 
    else: 
     oldsum, oldterm = _x(n-1) 
     newterm = 2*oldsum + 1 
     newsum = oldsum+newterm 
     return (newsum, newterm) 

def x(n): 
    return _x(n)[1] 

例：

>>> x(1) 
(1, 1) 
>>> x(2) 
(4, 3) 
>>> x(3) 
(13, 9) 
>>> x(4) 
(40, 27) 
>>> x(5) 
(121, 81) 

混乱が新しい合計/用語対古いあったかもしれません。