Author Topic: [C Tutorial] Recursion  (Read 3178 times)

0 Members and 1 Guest are viewing this topic.

Offline Rafy

  • Peasant
  • *
  • Posts: 112
  • Cookies: 4
    • View Profile
[C Tutorial] Recursion
« on: December 14, 2011, 10:22:05 am »
Hello guys ,
I decided to do an example about recursion cause it's an argument I had difficulty understanding
at first.So what is recursion in programming?

Recursion is a programming technique that allows the programmer to express operations in terms of themselves. In C, this takes the form of a function that calls itself. A useful way to think of recursive functions is to imagine them as a process being performed where one of the instructions is to "repeat the process". This makes it sound very similar to a loop because it repeats the same code, and in some ways it is similar to looping. On the other hand, recursion makes it easier to express ideas in which the result of the recursive call is necessary to complete the task. Of course, it must be possible for the "process" to sometimes be completed without the recursive call. One simple example is the idea of building a wall that is ten feet high; if I want to build a ten foot high wall, then I will first build a 9 foot high wall, and then add an extra foot of bricks. Conceptually, this is like saying the "build wall" function takes a height and if that height is greater than one, first calls itself to build a lower wall, and then adds one a foot of bricks.

so here is an example I wrote for recursion so you can understand it better(I will post more examples as I code them)

Code: [Select]
/*rafy recursion example 1 */



#include <stdio.h>


void recurse (int count)
{
 if (count<9) /*We need a limit otherwise the program would execute till it crashes*/
 {
  printf("%d  \n",count);  /*prints the count on-screen*/
  recurse (count +1); /*calls the function recurse and adds 1 to the count*/
 }


}

int main ()
{
 recurse (1); /* the first time I call the function I put count=1 */
 return 0;
}




So here it goes for now.I know tail recursion is missing,when I learn that I will add a second part to the tutorial.
« Last Edit: December 14, 2011, 10:38:05 am by Rafy »
If it moves shoot it,if it runs... hack it!

Online ca0s

  • VIP
  • Sir
  • *
  • Posts: 426
  • Cookies: 52
  • Gender: Male
  • ca0s@ka0labs #
    • View Profile
    • ka0labs #
Re: [C Tutorial] Recursion
« Reply #1 on: December 14, 2011, 12:53:00 pm »
Nice. The classic example I was told when learning was calculating the factorial of a number:
Code: [Select]
#include <stdio.h>
#include <stdlib.h>

int f(int n)
{
  if(n<=2) return n;
  else return n * f1(n-1);
}

int main()
{
    printf("Factorial of 10: %i\n", f(10));
    return 0;
}

Offline Rafy

  • Peasant
  • *
  • Posts: 112
  • Cookies: 4
    • View Profile
Re: [C Tutorial] Recursion
« Reply #2 on: December 14, 2011, 03:24:19 pm »
arghhhhhhh!That's the one the prof told us too but it was too complicated (I never studied factorials) for me so i made up this example.
« Last Edit: December 18, 2011, 04:27:47 pm by Rafy »
If it moves shoot it,if it runs... hack it!

Online s3my0n

  • Knight
  • **
  • Posts: 259
  • Cookies: 54
  • Gender: Male
    • View Profile
    • ::1
Re: [C Tutorial] Recursion
« Reply #3 on: December 14, 2011, 03:43:55 pm »
Be careful with recursive functions, since for every function call a separate stack frame is made. This can lead to segmentation fault :P

Instead you can use a loop to do stuff like finding a factorial:
Code: [Select]
int fact(unsigned int n)
{
    if (n<=2) return n;
    unsigned int answer = 1;
    while (n != 1) answer *= (n--);
    return answer;
}
« Last Edit: December 15, 2011, 05:35:49 pm by s3my0n »
Easter egg in all *nix systems: E(){ E|E& };E

Online ande

  • Owner
  • King
  • *
  • Posts: 2460
  • Cookies: 222
    • View Profile
Re: [C Tutorial] Recursion
« Reply #4 on: December 17, 2011, 06:49:47 pm »
Be careful with recursive functions, since for every function call a separate stack frame is made. This can lead to segmentation fault :P

Instead you can use a loop to do stuff like finding a factorial:
Code: [Select]
int fact(unsigned int n)
{
    if (n<=2) return n;
    unsigned int answer = 1;
    while (n != 1) answer *= (n--);
    return answer;
}

Indeed, did a little bit of research on this not long ago (was arguing with my teacher lol). If I remember correctly, you will start having problems at aprox 75.000 to 100.000 calls.

Offline Rafy

  • Peasant
  • *
  • Posts: 112
  • Cookies: 4
    • View Profile
Re: [C Tutorial] Recursion
« Reply #5 on: December 18, 2011, 04:29:07 pm »
I know that that's why I put the "if" statement ,last time I didn't and the terminal screen was full of numbers. :P
If it moves shoot it,if it runs... hack it!

Online Deque

  • VIP
  • Baron
  • *
  • Posts: 826
  • Cookies: 286
  • programmer
    • View Profile
Re: [C Tutorial] Recursion
« Reply #6 on: December 19, 2011, 06:47:15 pm »
Quote
So here it goes for now.I know tail recursion is missing
Yours is a tail recursion.

Quote
Be careful with recursive functions, since for every function call a separate stack frame is made. This can lead to segmentation fault :P

Instead you can use a loop to do stuff like finding a factorial:
Or in case of tail recursion let the compiler optimize it. I.e. option -O3 for gcc will do it.

Offline Tsar

  • Peasant
  • *
  • Posts: 129
  • Cookies: 10
  • turing-recognizable
    • View Profile
Re: [C Tutorial] Recursion
« Reply #7 on: December 20, 2011, 12:20:53 am »
Yours is a tail recursion.

It is, but it doesn't really show the principle of it. It is a bad example to demonstrate both linear and tail recursion, because it doesn't return.

 



Intern0t SoldierX SecurityOverride programisiai
Want to be here? Contact Ande, Bluechill or Kulverstukas on the forum or at IRC.