Python: Create function without recursion

Question

I would like to create this function without recursion.

def fib2(n: int) -> int:
    if(n <= 0): return 0
    if(n <= 2): return n
    return ((fib2(n-1) * fib2(n-2)) - fib2(n-3))

Can anyone help me or explain how to solve this?

A recursive call repeats the same code, but with different arguments. So, you need a loop (to repeat the execution of the same code) and variables which hold values sent to the loop and results from the loop. — zvone, Dec 03 '20 at 17:50
Oh, I thought this was fibonacci, but it's some weird variation of it. — Barmar, Dec 03 '20 at 17:54
I've reopened, but I think the same principles in those answers can probably be used for this. — Barmar, Dec 03 '20 at 17:55
@Barmar Thnx and true, still this needs to keep track of 3, not 2 values, so think it can have instructive answers in its own right that are not immediately obvious to the beginner. — user2390182, Dec 03 '20 at 17:59
Another question about fibonacci with last 3 numbers: https://stackoverflow.com/questions/26921314/fibbonaci-like-sequence-of-last-3-numbers — Barmar, Dec 03 '20 at 18:00

user2390182 · Accepted Answer · 2020-12-03T18:02:12.667

1

One rather concise and Pythonic way to do it without any extra space requirements:

def fib2(n: int) -> int:
    a, b, c = 0, 1, 2
    for _ in range(n):
        a, b, c = b, c, (c * b) - a
    return a

You need to keep track of three values for the calculation and just keep rotating through them.

edited Dec 03 '20 at 18:02

answered Dec 03 '20 at 17:57

user2390182

72,016
6
67
89

score 0 · Answer 2 · answered Dec 03 '20 at 17:55

0

Find all the fib2 results from 1 to nn.

def fib2(nn: int) -> int:
  mem = {
    0: 0, # first  if
    1: 1, # second if
    2: 2  # second if
  }
  # now find all the fib2 results from 3 to nn
  kk = 3 
  while ( kk <= nn ) :
      mem[kk] = mem[kk-1] * mem[kk-2] - mem[kk-3] 
      kk++;
  return mem[nn]

answered Dec 03 '20 at 17:55

napuzba

6,033
3
21
32

1

Exercise to OP : you can do it in constant memory :-) – napuzba Dec 03 '20 at 18:02

Python: Create function without recursion

2 Answers2