Iteration vs Recursion – a Beginner’s approach

1. Introduction

Computer programming is about solving problems and getting things done the right way. However, as a beginner, you don’t care how you do it as long as you get it done. It works, so why bother tackling it in a completely different way after all?

I thought the same way when I first stumbled upon recursive programming in Swift since it behaves exactly like its iterative counterpart. So I approached it reluctantly at first and soon asked myself how I lived without it.

The biggest challenge you face when discovering new programming paradigms is changing the way you think. This can be scary at first because you are used to doing things in a certain way and now you suddenly feel overwhelmed. It takes time and patience to get used to anything new but it’s worth doing it in the long run – being able to choose the right technique for a certain problem is a skill that any software developer should have in his toolbox.

OK, enough talking – let’s see what recursion is all about.

2. The challenge

Your task for this tutorial is an easy one: compute the factorial of a given number. Before diving into coding, think how you would solve the problem and break it into steps. This is how I would do it:

  • create the factorial variable and assign its default value;
  • loop through the whole numbers from 1 to the given one and do two things for each iteration:
    • extract the current value from the loop;
    • add it to the factorial;
  • print the factorial to the console;

That’s it for the algorithm – now let’s move on to the implementation.

Note: If you skipped the Maths class in high school, you can read more about factorials here.

3. The iterative implementation

Fire up Xcode and open a playground. Delete everything from it and add this line to kick things off:

var factoriali = 1

This creates a factorial variable and sets its initial value – it is variable because you are going to change its value soon.

Note: There are many different ways of creating variables in Swift – this is the easiest approach of all because it uses type inference to determine the variable’s type – Int in this case.

Now loop through the numbers from 1 to 5 with the for in control flow statement using the closed range operator:

for i in 1...5 {

}   

Note: You can also write the loop using the half open range operator:

for i in 1..<6 {

}   

Note: There are many ways of looping in Swift – this is the best approach in this case because it gives you access to the current value for each iteration.

There is only one thing you should do inside the loop for each value – add it to the factorial:

factoriali *= i

Note: You could also do it like this – the initial approach is shorter because it uses the multiplication assignment operator:

factoriali = factoriali * i

Finally, print the factorial to the console:

print(factoriali, terminator: "")

Note: There are other ways to print to the console as well – this approach doesn’t print the newline “\n” character in the playground.

4. The recursive approach

Recursion is about using a concept in the context of its definition. The factorial is a good match, since you can think of it like this:

n! = 1 * 2 * 3 * … * n = (1 * 2 * 3 * … * n-1) * n = (n-1)! * n

Recursive programming means encapsulating the concept in a function of its own – so let’s do just that!

5. The recursive implementation

Create the function’s prototype:

func factorialr(n: Int) -> Int {

}

The function has the number as its parameter of type Int and returns the factorial as an Int.

There are two things you should do in the function’s body. First define the recursion’s stop condition:

if n == 1 {
        
    return 1
        
}

Here you simply return 1 if n is 1 since 1! = 1.

Note: You can take into account that 0! = 1 and write the condition like this using the logical OR operator – the initial approach is shorter though:

if n == 0 || n == 1 {
        
    return 1
        
 }

Note: If you forget this step you end up with a stack overflow error, since recursion behaves exactly like endless loops in this case.

Next implement the recursive rule and return the factorial:

return n * factorialr(n-1)

Note: If you think of factorialr(n) as n! and factorialr(n-1) as (n-1)!, it boils down to the mathematical approach we all know and love (or at least some of us do): n! = n * (n-1)!

Now print the factorial to the console – use 5 for the function’s argument to be consistent with the iterative implementation.

print(factorialr(5), terminator: “”)

That’s it – let’s analyse the implementation.

6. The recursive implementation analysed

Recursion isn’t straightforward and out of the box, so let’s see what happens under the hood step by step:

  • The first recursive rule is factorialr(5) = 5 * factorialr(4);
  • Then factorialr(4) = 4 * factorialr(3). If we combine the two, we have factorialr(5) = 5 * 4 * factorialr(3);
  • Next factorialr(3) = 3 * factorialr(2), hence factorialr(5) = 5 * 4 * 3 * factorialr(2);
  • Now factorialr(2) = 2 * factorialr(1), so factorialr(5) = 5 * 4 * 3 * 2 * factorialr(1);
  • Finally, factorialr(1) = 1, thus factorialr(5) = 5 * 4 * 3 * 2 * 1 = 120, since 5! = 120;

7. Iterative vs recursive comparison

Iterative advantages:

  • clear steps
  • easy to understand

Iterative disadvantages:

  • certain tasks can be treated more elegantly in a recursive manner

Recursive advantages:

  • compact approach – each step is solved based on what you know already
  • easy to infer from its mathematical counterpart

Recursive disadvantages:

  • not all concepts can be modelled in a recursive fashion

8. Conclusion

Both paradigms have their pros and cons – feel free to try them both and choose the one that suits you best. Happy coding! 🙂

Note: All the code in this tutorial was tested in a playground in Xcode 7.2 and Swift 2.1 (Download).

Advertisements
Posted in Swift

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to receive notifications of new posts by email.

Simple Programmer
%d bloggers like this: