Notes about recursion

posted in: C, Guides, tricks | 0

In order to understand recursion, you must understand recursion.

A common approach of solving life’s problem is to divide them in smaller ones. Solving lot of little problems is easier than solving one big problem. This approach is often used in programming and is more known as  divide and conquer.

Simple example

For example let’s write a factorial function. In a normal way of thinking, you would use a loop to get to the result. Like this way:

But if you see the problem in another approach , you could multiply the result of the needed factorial with the result of the lower factorial. Little by little you will arrive in the case of the only factorial we know: 0! = 1. While n > 0 we multiply n with the factorial of n- 1. In code this could be sum up in:

In recursion, you should never forget about having a stop case! In case you forget you will fall into an infinite loop which may cause your program to crash.

Another common example is the Fibonacci numbers that are defined recursively.

 

Wrapper function

In some case you may need to write a wrapper function. What is wrapper function? This is function that will call a recursive function with the needed parameters. For example the function to check if a given string is a palindrome. (A palindrome is a string which is symmetric in its center for eg: “abba”, “azerreza”…)

 

Recursion data structures

Recursion data structures are structures where data relationship is defined by recursion. Like ordered binary tree where left child is lower than its parents and right child is greater than it’s parents. This is also true for the parent.

In this type of data structure it is often easier to manipulate them with recursion than iterative way.

 

More reading

Here is a list of links I found interesting about recursion:

http://stackoverflow.com/questions/5631447/how-recursion-works-in-c

http://www.wikipedia.com/en/Recursion_(computer_science)

http://stackoverflow.com/questions/15518882/how-exactly-does-tail-recursion-work

http://cs.stackexchange.com/questions/1418/when-to-use-recursion

http://cs.stanford.edu/people/eroberts/courses/cs106b/chapters/05-intro-to-recursion.pdf

Leave a Reply