C++ Recursion Examples

Compiled and Debugged by: Diego 28. Mar, 2010 View Comments

C++ Recursion Examples

Recursion is often one of those topics in programming that many people fail to grasp immediately due to its nature. If you don’t remember, recursion in C++ is simply a function that calls itself that terminates when a base case is met.

But, why can learning this subject be difficult? Since a recursive function may have many and often an unknown amount of recursive calls, its difficult to trace its behavior. The biggest mistake I see when people try to create or traverse these functions, is when they try to do it in their head. If you are a beginner, I recommend you to get rid of this habit and learn to write your ideas down. Trust me, you’ll save yourself time.

The recursive calls of Fibonacci when n = 4

Getting Started

Below are a couple of examples to help you learn the process. Before you view them, try working them out on your own. This is always the best way since you’ll develop a method you’ll always remember. Only once you gave it your best effort and couldn’t solve it, go through the examples. Make sure you understand the thought process presented, because once you understand it writing recursive functions should be a lot easier.

Beginner C++ Recursion Examples

Below are some basic examples using recursion. These should teach you the basics on base cases, and return statements.

Printing a Sequence of Numbers in Reverse
By now you should know how to print a sequence of numbers using recursion. What about printing this same sequence in reverse? This should require a minor change to your previous recursive function.
C++ Recursion – Printing a sequence of numbers in reverse

Summation
Let’s try doing some math using recursion. Can you create a function that computes the summation of 0, 1, …, n – 1, n ? This basic recursive function should help you understand how recursion can be used.
Example:

C++ Recursion – Summation

Factorial
Did you understand how the summation function worked using recursion? Try making a function that computes n factorial.
Example:

C++ Recursion – Factorial

Intermediate C++ Recursion Examples

These intermediate examples require a little bit more thinking since you are dealing with more parameters into your function headers.

Power
Now that you have a good grip of simple recursive functions, try your hand at something a little bit more difficult.
Example:

C++ Recursion – Power

Greatest Common Divisor
Can you determine the greatest common divisor or two numbers? The example is done using Euler’s formula.
Example:

C++ Greatest Common Divisor

Logarithm
Previously we asked you to do a Power function, now something similar. Try doing the logarithm of base 2, and of base n.
Example:

C++ Recursion – Logarithm

Fibonacci
Given a definition of a math function, could you come up with a recursive function?

C++ Recursion – Fibonacci

Advanced C++ Recursion Examples

The following recursive functions are a little more complex since they require a bit more of planning.

Reverse elements of a vector
Given a vector, can you reverse the order of the elements using recursion?
C++ Recursion – Reverse elements of a vector

Determining if a string is a palindrome
Can you determine if a string is a palindrome? A palindrome is a string that can be read the same both forward and backwards such as racecar, mom, and abba.
C++ Recursion – Palindrome

Binary Search
Can you perform binary search using recursion?
C++ Recursion – Binary Search

Going Further

Remember, practice makes perfect. Recursion is a difficult subject so don’t give up early. Just make sure you develop a method to tackle recursion. Once you have one down, recursion shouldn’t give you trouble.

If you wish to see more examples, post them below.