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
– zvone, Commented Dec 3, 2020 at 17:50
Oh, I thought this was fibonacci, but it's some weird variation of it. — Barmar
– Barmar, Commented Dec 3, 2020 at 17:54

user2390182 · Accepted Answer · 2020-12-03 18:02:12Z

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 3, 2020 at 18:02

answered Dec 3, 2020 at 17:57

user2390182

73.7k6 gold badges71 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

napuzba · Accepted Answer · 2020-12-03 17:55:55Z

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 3, 2020 at 17:55

napuzba

6,3183 gold badges24 silver badges34 bronze badges

1 Comment

napuzba Over a year ago

Exercise to OP : you can do it in constant memory :-)

Collectives™ on Stack Overflow

Python: Create function without recursion

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related