Recursive Fibonacci

Question

There is this question in Python Core , how should I code only in the function block to print the numbers only once?

----------
The Fibonacci sequence is one of the most famous formulas in mathematics.
Each number in the sequence is the sum of the two numbers that precede it.
For example, here is the Fibonacci sequence for 10 numbers, starting from 0: 0,1,1,2,3,5,8,13,21,34.

Write a program to take N (variable num in code template) positive numbers as input, and recursively calculate and output the first N numbers of the Fibonacci sequence (starting from 0).

Sample Input
6

Sample Output
0
1
1
2
3
5

If you are making the Fibonacci sequence for n numbers, you should use n<=1 condition as the base case.
----------

I passed with this code, but it is not a recursive function.

num = int(input())

def fibonacci(n):
#complete the recursive function
p, q = 0, 1
for i in range(n):
print(p)
p, q = q, p + q

fibonacci(num)

Answer 1

According to software design principles, any unit of code should have only one purpose (single responsibility principle).
Recursion relies on the output (return value) of the same function to build up the solution. So it is not a good idea to mix the printing into any function whose purpose is to do some calculation and return a result.

To calculate Fibonacci sequence recursively, you need to add the last two elements. You can express this like fib(n-2) + fib(n-1)
Adding the base case, you can write a recursive function which calculates and returns the n-th Fibonacci number. Then it is best to print them outside the function.

def fib(n):
if n < 2:
return n
else:
return fib(n-2) + fib(n-1)

for i in range(8):
print(fib(i))

There are much more efficient ways to do this, memoization (remembering results that are already calculated) is a key part of using recursion.

https://code.sololearn.com/c578o3uoLhym/?ref=app

Answer 2

Ausgrindtube yes, I get it, and unfortunately this is not the only place where the lesson contents or examples are implying bad coding habits and bad practices. That's why I feel responsible for speaking up, if I know a better way.

Answer 3

Using 100% of the original snippet and still keeping a pure recursive approach, this can be solved with a nested inner function.

https://code.sololearn.com/cptbuW73uqLO/?ref=app

The inner def could even be expressed as a recursive lambda:

f = lambda n: n if n<2 else f(n-1)+f(n-2)

Answer 4

Printing is an impure "side effect" of a calculation, and should be avoided according to functional programming principles, especially in recursion.

Answer 5

Awesome!

Btw, can we call a inner function directly?

Answer 6

Since the base code was
```
num = int(input())

def fibonacci(n):
#complete the recursive function

fibonacci(num)
```
I wanted to complete it with the constrains adding code only inside the function block and making it a recursive function. 🥹

Very nice code there. And thanks for introducing that powerful tool.

Answer 7

Lochard you had the same problem I had. 😅

https://www.sololearn.com/discuss/3180635/?ref=app

Answer 8

Inspired by the answer of Lisa in the post of Ausgrindtube.
I came up with a messy solution.

https://code.sololearn.com/cV9LV8Uk85k0/?ref=app

Answer 9

You are definitely a fountain of knowledge and I know I value your input, thanks.

Answer 10

o.gak Thanks, I understand now. Took me a long time and some tests. 😵

Answer 11

Lochard You may want to read this first.

9.2. Python Scopes and Namespaces
https://docs.python.org/3/tutorial/classes.html#python-scopes-and-namespaces

Answer 12

Tibor Santa I understand what you mean. It's just that the code snippet supplied and the better solution don't match and so one feels like they are doing something incorrectly or incompletely by not using the code snippet provided.

Answer 13

Lochard Ausgrindtube
To be strict to the base code of the course, I tried this ⬇️

https://code.sololearn.com/cYYe9ir7GUuE/?ref=app

Answer 14

o.gak I don't understand why your fibonacci_forward() won't print numbers repeatedly.

Answer 15

Lochard
Yes, but still only print `f(n-1)` in each recursion.
`need_print and n >= 2` will be True only when the parameter `need_print` is True.
`need_print and n == 2` will be False when n > 2.

Answer 16

Lochard
When n > 2, I will only print `fNumPrev1` which means `f(n-1)`.
When n == 2, I will print both `fNumPrev1` which means `f(n-1)` i.e. `f(1)` and `fNumPrev2` which means `f(n-2)` i.e. `f(0)`.

Answer 17

And there should be multiple calls with n >= 2 (outside the function called), shouldn't it?

Answer 18

Lochard It took me a long time to write this too. 😅

Answer 19

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

num = int(input())

for i in range(num):
print(fibonacci(i))

Answer 20

Azeez Khan Thanks. We just wanted to do it the hard way.