Rewriting recursive stuff

Computer Science
1

hey, I was doing this work to rewrite a recursive function for a Fibonacci sequence but I dont understand the method taken at all. could someone explain?

Thanks!

Screenshot (5)
Screenshot (5)1920×1080 243 KB

2

i have gotten onto writing recursive functions and am also finding issues here. I understand recursion but i’m finding it difficult to know what to do when writing the functions themselves. not sure if anyone has tips and tricks or can explain a strategy or knows any videos that might be helpful that’d be great!

Screenshot (6)
Screenshot (6)1920×1080 225 KB

3

I am still learning too so I am not sure if this will help, but that’s how I think about it.

Recursive
The idea behind recursive is to break a problem to smaller problem until solving it becomes so easy. To do so, we must do two things:

  1. Decide the base case. The base case is the smallest problem we can get after breaking the original problem.

  2. Decide how we will break the original problem to smaller problems. This is probably the hardest part when implementing recursive. To do this part correctly, you have to think how to get from the original problem to the base case.

Fibbonaci
We need to implement a function that tells us what is the nth element in the following sequence: [1, 1, 2, 3, 5, 8, 13, 21, 34, …, n]. As you may already know, the rule for this sequence is n = (n-1) + (n-2). That is, the nth element is equal to the sum of the two elements before it. This means to find n, we need first to find (n-1) and (n-2). But to find (n-1), we also need to first find (n-2) and (n-3) and so on.

This means to find the nth element in the fibbonaci sequence, we need to go back to beginning of the sequence (at n = 1) and keep generating elements until we reach the nth element we need.

To implement this in Python, we need to determine the two main things I mentioned when explaining recursive:

  1. the base case: we know that the first element (at n = 1) is equal to 1. So our base case is
if n == 1:
  return 1

But also we need to account in case n < 1. In this case, we need to just return 0. So, we will add another base case:

if n < 1:
  return 0
  1. Now, let’s decide how to break the problem to smaller problems. To find the nth element, we need to find the two elements before it: (n-1) and (n-2). To find (n-1) and (n-2), we simply call the fibonacci function again and passing them as arguments. This step will repeat until we reach the base case (n = 1 or n < 1). After we reach the base case, the function will return a value (1 or 0 as stated in the base case). This value will be used to find the next element in the sequence which also will be used to the find the following element and so on.

The final code becomes:

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

Finally, let me know if there is anything unclear.

1 Like
4

Thanks for this, I do understand the Fibonacci one, of all examples it seems like an easier one as it’s clear that it’s the number before ‘n’ and two numbers before that need to get added up. I also do know the rules of writing the functions , I’ve watched a couple videos which did help.

But it’s actually writing these functions after reading the instructions of what I need to make a recursive function out of that I struggle with. I am often along the right lines but I fear that I will never be able to write one without help and obviously that wouldn’t be beneficial.

5

I think at this point all you need is just practice. You can look for problems that have recursive solutions and try to solve them by yourself. You can find such problems easily on internet. For example, you can go to LeetCode, problems, search “Recursion”, and start by solving the “Easy” problems then the “Medium” and “Hard” ones.

1 Like
6

That sounds good, thanks for the help and suggestion of that website, appreciate it !

1 Like