Recursive Functions

About the very basics of recursive function and stack overflow.

The  two pictures above form the essence of this blog. Essentially, we will look at what recursion is. It’s  a good idea to read about Functions and Stacks before going ahead.

In this write-up I plan to cover what recursion is , how you could write your own recursive function, things to be wary of while using recursive functions and of course a take on recursion versus iterative methods.


What is Recursion ?

Recursion refers to self-referencing. If a given problem can be solved for input “n”,  by representing the the solution for case “n” in terms of calls to the same function for cases other than “n”, it is recursive!

So in essence, recursive functions refer to functions that call themselves repeatedly until an exit condition is met. Note : If you forget an exit condition, the function will run forever eventually resulting in stack over flow !!

There are also recursive data types (structures that have an element of their own type, example linked list) that we will not be looking at today.

Writing your own recursive functions

One of the tricks to writing recursive function is to understand the pattern in the problem and creating a “recursive formula “or the “recursive action” you need to perform.

Let’s consider a really basic example. Say you need to write a function that will take an input “n” and return the (n)th odd number in the arithmetic series of odd numbers.

Now, let’s take a few input values “n” (call it the input Term) and the corresponding odd number f(n) (the Value we are looking for) in Fig (1) below under Block A. Looking at the table, we can identify a generic pattern that (n)th number is the previous value plus 2. So, we get a generic recursive formula : f(n) = f(n-1)+2 , essentially value (f(n)) for input term “n” is the previous value (i.e., f(n-1))plus 2.

We can use this recursive formula to write our recursive function for positive integer inputs, as shown in Fig(1) below under Block B.

recur.png

Fig(1). Recursion function and Recursive formula

A recursive function can be split into two blocks of execution:

  1. The Base case that is required in all recursive functions – for this defines the EXIT condition. We should know when to terminate the recursive call. There may be one or more base cases for our recursive function.
  2. Remaining part of the function shall contain recursive call to self and in some cases post processing is also required after the recursive call [example, in this case is “adding 2” operation after the recursive call]

Referring to Fig(1), for the base condition, we can take a trivial case as input. Let’s take n=1 case as the base or exit condition, the first odd number to be returned is 1.

For other cases, we can return expected value using the generic recursive formula we derived. Suppose your function is called oddNumber(n) instead of f(n), then the else part in Fig(1) Block B, shall be :

return oddNumber(n-1)+2;

This technique can be reversed to decipher what a recursive function does. If you are given a recursive method, all you have to do is look for the recursive formula in the function and start substituting valid value terms  “n” to be passed, starting with the base case values. The substitution method shall help you get an idea of what the function value represents, in the example,we can see that the values are all odd numbers and know that the function essentially returns nth odd number for given input n.

Other common examples of recursive functions-

  • Fibonacci series :

Expected value f(n)  : 1,1,2,3,5,8 and so on … 

Fibonacci value f(n) at nth position is a function of previous two values f(n-1) and f(n-2)

Recursive formula for Fibonacci is : f(n)=f(n-1)+f(n-2)

Base case here requires at least two values, so n=0 and n=1 case which return 1, shall be considered the exit condition when we write recursive function

  • GCD of two numbers : Greatest common divisor , highest common factor or the highest common divisor.

Greatest common Divisor is given by Euclid’s formula (the recursive formula to be used) : gcd(x,y) = gcd(x, x%y), recursive calls end when second term is zero ( or y is zero) , when y is zero, x is the greatest common divisor.

  • Same principle can be extended to  tree or graph traversals. Will be covering these in another blog.
  • These are the real use cases where we would prefer a recursive implementation 😉

Before we go to the next section, I have one question for you to solve.

What does the recursive method below do assuming input n is a power of 2 ? 🙂

Mail me the answer at decodergirlblog@gmail.com

// Note : Assume n is a power of 2 and log is base 2.

int func ( int n ){

if(n<=2) {

return 1;

}

else{

return func(n/2)*log(n);

}

} // end of function


Iterative or Recursive

Iterative refers to implementation using no self referential calls,implemented using loops.

From this blog entry , we know that the stack keeps growing as and when function calls are made. This holds good for recursive functions as well. A stack frame is allocated for each invocation of the recursive function. This means to say, there will be “n” stack frames allocated for an input “n”.  If we miss an exit condition or the base case,  there will be no end to the recursive calls, and because of the allocation of stack frames plus the fact that stack memory is limited resource, we will run out of stack space resulting in “stack overflow”. If you are a memory constrained system, you would be better off getting rid of recursive calls for solving trivial problems (Fibonacci, factorial etc), iterative will not allocate any extra memory, it will only update the loop variables in these cases. But, recursive functions offer cleaner, elegant solutions for problems involving “divide and conquer” technique (merge sort) and also the tree traversal problems.

We would need to know the depth of recursion we are aiming for and the stack memory available and the time constraints we need to work with before we think of recursive solutions. Essentially, know the constraints you have to work with. Recursive solutions take extra space and also extra time (due to usage of system stack) for solving the problem, but offer cleaner looking and/ elegant solutions.

Now, think of this :

What if we have a way to get the space consumption as in iterative case and also have the elegance of a recursive function : this is an optimization for recursive functions – called the tail recursion !

Will be writing a tidbit about this soon. Until then, keep decoding !

  1. # public domain
    function recur x
        ifless x 5
            now = x ; plus 1
            x = "this is great! " ; times now ; print ; recur now
            fig
        fig
    
    now ; recur 0

    great post, very accessible– definitely want to hear about tail recursion.

    Liked by 1 person

    Reply

    1. Thank you for reading it! 🙂
      Tail recursion – Soon 🙋

      Also, I am now curious about fig coding ! 🤓

      Liked by 1 person

      Reply

      1. well, the second version of the book is in progress, this is chapter 1: https://codeinfig.wordpress.com/2016/05/23/variables-in-fig/

        and if you make it through the 7 chapters, (or even if you dont) i can link you to the pdf of the draft version, which also includes “debugging,” a mini intro to python, and sample code.

        for a basic explanation: https://codeinfig.wordpress.com/2016/02/10/what-is-fig/

        a teaser: “although you may be able to use fig for years and years, it is designed for optional use as a transitional language– changing the underlying python only with sufficient cause, and offering an inline-python feature.

        fig has fewer than 100 commands, and follows basic-inspired, “all-purpose” language goals. my hope is that fig is easier to teach than any other language.” <- or perhaps inspire the next educational language.

        Liked by 1 person

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

%d bloggers like this: