Now that SocialShield is part of the larger Avira family, we’re eager to introduce our users to antivirus software, coding and all things tech! To start, here’s a coding problem recently posted by Noah Kindler, SocialShield founder and true Techxpert:

Just for fun, here’s a neat coding problem and solution. Problem: Implement the nth Fibonacci number recursively. Read just as far ahead as you need if it helps, and please let us know if you find bugs or better solutions!

Solution: int finNum(int num) {…}

This is a canonical recursive problem that can be encountered. Let’s start this problem with a review of the Fibonacci sequence. This is a sequence of numbers where each number is the sum of the previous two numbers, and the first two numbers in the sequence are 0 and 1.  

A mathematician expresses this as:

Now, let’s do an example of the first say, 7, Fibonacci numbers to make sure that we get the pattern:

0 1 1 2 3 5 8

And we could go more.  

Well, with this, it seems set up for recursion. We have our two base cases, which is if the num is 1 or 2. And, otherwise, we have the sum of the two previous numbers.

With this, we can code it up, and we need to check for base cases:

int fibNum(int num) {

  /* Check for the error case of negative number or 0 */   if (num <= 0) return ERROR;

  /* Now, enter the two base cases */   if (num == 1) return 0;   else if (num == 2) return 1;

  /* and now, recursive call to figure out the number */   else return (fibNum(num-1) + fibNum(num-2)); }

And, that’s it. Let’s do an example, say 7 above, and walk through it to make sure that it works.

It does!

So, this solution works recursively. What is it’s runtime?

Well, it calls fibNum two times more as num grows. This means that the function is O(2^n). This is horrible for even small sizes of n. Wow. Just awful!

Think about how to make this better, while still recurring.