More Recursion in C

Recursion is a repetitive process where a function calls itself directly or indirectly. A function is directly recursive when it calls itself from within its scope, and it is indirectly recursive when it calls other functions that eventually calls it back.

In general, we use two approaches to writing repetitive algorithms. The first approach is the iterative approach using loops, the other uses recursion.  For example, let’s consider a factorial:

factorial (n) = 1 if n = 0
                n * (n -1) * (n -2) ... 1 if n > 0

A repetitive function is iterative when the definition of the function involves only the parameters and not the function itself. A repetitive function is defined recursively whenever the function appears within the definition itself. To look at factorials again, we would define them as:

factorial(n) = 1 if n = 0
               n * factorial(n - 1) if n > 0

 

We will write two functions, one two solve the factorial problem in an iterative manner, and the other to solve the factorial problem in a recursive manner.

#include <stdio.h>
#include <stdlib.h>

long itFactorial(int n){
    int i;
    long rValue = 1;
    for(i = 1; i <= n; i++){
        rValue = rValue * i;
    }
    return rValue;
}

long recFactorial(int n){
    if(n==0) { return 1;}

    return n * recFactorial(n-1);

}

int main()
{

    printf("%li\n", itFactorial(7));

    printf("%li\n", recFactorial(7));

    return 0;
}

Recursive functions have two elements, solving one part of the problem, and/or reducing the size of the problem. The call that delivers a definitive solution is known as the base case. Every recursive function must have a base case.

When implementing a recursive function, we should bear in mind how the function’s arguments are put on the stack. The stack frame grows by push operations caused by function calls, and it shrinks by pop operations by function returns. Each call gets a fresh copy of automatic variables that are totally independent of the previous set of values.

A popular example of a recurrence relation is the Fibonacci sequence, in which a number is the sum of the previous two numbers. The first few numbers of the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. To start the sequence, we define the first two numbers as 0 and 1, so that the third number is also 1 (0 + 1), and the fourth number in the sequence is 2 (1 + 1).

We will see two examples of the recursive Fibonnaci function.

#include <stdlib.h>
#include <stdio.h>

int fibA(int iParam){
    int rValue;

    //base case for 0 and 1 in the sequence
    if(iParam == 0 || iParam == 1) { return iParam; }

    //calls itself twice
    rValue = fibA(iParam - 1) + fibA(iParam - 2);

    printf("Returning %d\t", rValue);

    return rValue;
}

int fibB(int iNum, int iPrevOne, int iPrevTwo){
    int rValue;

    if(iNum == 0){
        printf("iNum == 0, returning %d\n", iPrevTwo);
        return iPrevTwo;
    } else if (iNum == 1){
        //when count reaches 1, returning back the final number
        //reached by adding iPrevOne and iPrevTwo
        printf("iNum == 1, returning %d\n", iPrevOne);
        return iPrevOne;
    } else {
        printf("%d, %d, %d\n", iNum-1, iPrevOne + iPrevTwo, iPrevOne);
        rValue = fibB(iNum-1, iPrevOne + iPrevTwo, iPrevOne);
        return rValue;
    }
}


int main()
{

    int i = 0;

    printf("\nfibA(5) = %d\n", fibA(5));
    printf("\nfibA(8) = %d\n", fibA(8));

    printf("\nfibB(7) = %d\n\n", fibB(7, 1, 0));
    printf("\nfibB(9) = %d\n", fibB(9, 1, 0));

    return 0;
}

We can also use a recursive function to find the greatest common denominator. The function will return the second parameter if the first parameter modulo the second parameter is 0, meaning that they divide evenly. Otherwise, the function will call itself, with the second parameter as the first argument, and the remainder of the modulo operation as the second argument.

#include <stdlib.h>
#include <stdio.h>

int findGCD(int a, int b){
    int remainder;
    if((remainder = a % b) == 0){
        return b;
    }
    return findGCD(b, remainder);
}


int main()
{
    printf("The GCD of 100 and 8 is %d\n", findGCD(100, 8));
    printf("The GCD of 150 and 5 is %d\n", findGCD(150, 5));

    return 0;
}

One of the most famous examples of a recursive s0lution is the Towers of Hanoi problem, but we will look at that at another time.

 

 

 

 

Advertisements

Simple Recursion in C

Certain objects in mathematics can be defined by the process that creates them, rather than as the end result itself. For instance, pi is defined as the ratio of the circumference of a circle to its diameter. When we think about it, pi is really defined as an algorithm – find out the circumference of a circle, then find out its diameter, then divide the circumference by the diameter. When we have an algorithm that produces a definite result, the algorithm itself can stand in for the result. In C, an algorithm that produces a result is a function, and, after all, we can in C and most C-family languages use a non-void function in place of a value, as long as the return type of the function is compatible with the type of the value we would have otherwise used.

Another example would be a factorial, represented as n!, where n is a positive integer. A factorial is defined as the product of all integers between the specified number and 0. For example, 3! = 3 * 2 * 1, which is equal to 6. While factorials are a pain to compute by hand, computers do them quite nicely, using a trusty loop.

#include <stdio.h>
int factorial(int n);
int main(void){ int num = 3; //3! printf("%d! = %d\n", num, factorial(num)); //increment num num++; //4! printf("%d! = %d\n", num, factorial(num)); printf("Note bene!:\n"); printf("%d! = %d * %d! ", num, num, num-1); printf("= %d\n", num * factorial(num-1)); return 0; }
int factorial(int n){ //use an iterative function for(int i = n - 1; i > 0; i--){ n*=i; } return n; }

 

Our first algorithm for producing a factorial is called an iterative algorithm; it calls for the repetition of a process until a condition is met. But, as we saw above, the factorial for a number is equal to that number multiplied by the factorial of the one less than itself. We can therefore describe a factorial as a chain produced by multiplying each positive number by the positive number before it; of course, this is verbally how we would describe the algorithm, but when it comes to writing it our first instinct is to write, for instance, 3! = 3 * 2 * 1, where we write the entire chain out at once. However, what if the number is 4, or 5, or 10, or 100?

We could generalize it as n! = n * n-1 * n-2 * etc etc * 1, or, strictly speaking, n! = n * n-1 * … * 1, with the three periods representing the implied intermediate values. As an easier shorthand, we can describe a factorial instead as n! = n * n-1!; this is a more exact representation of the verbal recipe we gave for arriving at a factorial – ‘multiply each whole number by the whole number preceding it, till we reach zero”. Defining an object in terms of a simpler case of itself is known as a recursive definition.

The thing is, though, doesn’t recursion go on forever? If Charlie Kaufman screenplays have taught us anything, it’s that the self-referential loop just goes backwards and backwards until we lose our minds.  Well, fear not, because just like an iterative loop, a recursion has a condition known as the base case that ends the loop. In the case of a factorial, !0 returns 1.

There’s an old joke that goes, “the key to understanding recursion is understanding recursion”. While humorous, this is, as far as I can tell, somewhat inaccurate, since there is no base case. In fact, in perhaps reinforces the false impression that recursion produces an infinite, self-referential loop. I would argue that a more useful reformulation would be “The key to understanding recursion is understanding recursion, unless you don’t understand recursion, in which case the key to understanding recursion is understanding the role of the base case, value-returning functions being treated as variables, and functions resolving first in, last out.” However, all that would probably not fit on a T-shirt.

#include <stdio.h>


int factorial(int n);

int main(void){
int n = 4;

printf("%d! = %d\n", n, factorial(n));

n--;

printf("%d! = %d\n", n, factorial(n));

return 0;

}


int factorial(int n){
//use a recursive function
if(n>1){
return n * factorial(n-1);
} else {
return 1;
}
}

One of the keys to grasping recursion in C is to remember that a value-returning function can be used in place of the value; this works because a called function must always resolve itself before the called function can resume executing.

Another fun example is to define the multiplication of positive integers recursively. Multiplication is, after all, just a weird kind of addition. If we take x * y, we see that it is really x plus itself y times.

#include <stdio.h>

int multiply(int x, int y);
//recursive version
int multiplyRecursively(int x, int y);

int main(void){
int n = 10;

for(int i = 1; i <= 10; i++, n--){
printf("%d * %d = %d\n", i, n, multiply(i, n));
printf("%d * %d = %d\n", i, n, multiplyRecursively(i, n));
}

return 0;
}

//iterative function
int multiply(int x, int y){
int val = x;
while(y-- > 1){
val+=x;
}
return val;
}

//recursive function
int multiplyRecursively(int x, int y){
if(y > 1){
return x + multiplyRecursively(x, y-1);
} else {
return x;
}
}

As our final example, we will take a look at the Fibonacci sequence.  The Fibonacci sequence is when we get a number by adding the two previous numbers in the sequence, and to start the sequence off, the first number is 0 and the second number is 1. Thus, the sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … We can view a Fibonacci sequence as being a function, we are willing to define f(0) as equalling 0 and f(1) as equalling 1; in other words, in the case of 0 or 1 the function returns its argument.

What about 2? Well, f(2) = 1 + 0, which also happens to be f(1) + f(0), so we can say that f(2) = f(1) + f(0). What about 3? Well, f(3) = 1 + 1, which happens to also be f(2) + f(1), thus we can say f(3) = f(2)+f(1), remembering here that f(2) = 1 and f(1) = 1. What about 4? Well, f(4) = 2 + 1, and since f(3) = 2 and f(2) = 1, we can say that f(4) = f(3) + f(2). For any element in the sequence, then, we can say that f(n) = f(n-1) + f(n-2), where f(0) = 0 and f(1) = 1. Or, if we really, really want to, we can say that f(n) = f(n-1) + f(n-2), where f(n) = n if n = 0 or n = 1.

#include <stdio.h>

int fib(int a);

int main(void){

for(int i = 0; i < 10; i++){
printf("Fib. num. for %d is %d\n", i, fib(i));
}

return 0;

}

int fib(int a){

if(a <= 1){
return a;
} else {
return fib(a-1) + fib(a-2);
}
}

Do you have $2.99 and a tablet, computer, or Kindle? Purchase a copy of my book on C, it’s viewable on just about any glowing screen you can think of. Over 100 example programs and explanations that are, I swear, far more lucid that the ones you find on this blog. http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M/