Using recursive functions (I am beginner at C programming)

This is a discussion on Using recursive functions (I am beginner at C programming) within the C Programming forums, part of the General Programming Boards category; Okay so the job of this program is to have a robot take steps of 1,2,3 meter in a amount ...

  1. #1
    Registered User
    Join Date
    Feb 2013
    Posts
    18

    Using recursive functions (I am beginner at C programming)

    Okay so the job of this program is to have a robot take steps of 1,2,3 meter in a amount of steps asked by the user. After the user inputs a value, the program will tell them that the robot can walk "user input" meter in a certain amount of ways.
    Example:
    If the user enters "4"
    The program enters 4 meters and uses a recursive function to print how many steps it will take.

    To Travel 4 meters, a robot has 7 ways to do it
    This is the part I have down right now
    The other part is to display all of the possibilities. So after that is printed

    1 1 1 1
    2 1 1
    1 2 1
    1 1 2
    2 2
    1 3
    3 1

    would print.

    How do I go about printing this part of the code?
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    int walk(int distance);
    main()
    {
    	int d,count;
    	printf("A robot can walk 1,2 or 3 meter at a time\n");
    	printf("This program will give all the possible combinations the \n robot can walk \n");
    	printf("\n How far would you like the robot to walk? ");
    	scanf("%d",&d);
    	if (d<1)
    		printf(" \n A robot can not walk a negitive distance \n");
    	else{
    		count = walk(d);
    		printf("The robot can walk %d meters in %d ways. \n",d,count);
    		getchar();
    		getchar();
    	}	
    }
    int walk(int distance)
    {
    	switch (distance){
    		case 1:
    			return 1;
    		case 2:
    			return 2;
    		case 3:
    			return 4;
    		}
    return walk(distance-1)+walk(distance-2)+walk(distance-3);
    }

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,765
    What happens if you write it out backwards, to see the pattern you would get if called recursively

    3 1
    2 2
    2 1 1
    1 3
    1 2 1
    1 1 2
    1 1 1 1

    On each recursive call, you're decrementing the number in column n, and incrementing the number in the column to the right.
    When you end up with a 1 in the right most column, you can go no further, the recursion ends and backtracks up to a previous column that can be incremented.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Feb 2013
    Posts
    18
    Okay, I am understand how to go about the solution, it is clearer to see with the answers being backwards. I am going to write the program part of this later on and i will respond back if I have trouble (brain is fried)

    Thank you

  4. #4
    young grasshopper jwroblewski44's Avatar
    Join Date
    May 2012
    Location
    Where the sidewalk ends
    Posts
    294
    *Noting this exercise for me to practice recursive functions.

  5. #5
    Registered User
    Join Date
    Feb 2013
    Posts
    18
    I am having a terrible time figuring out how to start this.
    Code:
    int combination(int a,int count)
    {
    	if (count <=1){
    		printf("%d",a);
    		return a;
    	combination(a+1,count-1);
    	printf("%d",a);
    	}
    }

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,765
    Start with this idea (you may need to add extra parameters)
    Code:
    combination(int a[],int pos) {
       ....
       combination(a,pos+1);
    
       ...
       // use a for loop to print from a[0] to a[pos]
    }
    
    int a[4] = { 4, 0, 0, 0 };
    combination(a,0);
    What you decide is when to recurse, and when to print.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    Feb 2013
    Posts
    18
    I don't have any experience in arrays yet for this project so I can't use this.

    Code:
    int combination(int a,int pos,int count)
    {
    	int d;
    	if (count>0)
    	{
    	
    		for (d=pos;pos!=0;--pos){
    			printf("%d",a);
        	}
        	printf("\n");
        	pos=d;
        	a++;
        	count--;
        	combination(a,pos,count);
    	}
    }
    Okay, so I got my code to run
    1111
    2222
    3333
    4444
    where count is the number of combinations in main and pos is the number entered by the user. Now how do I change what i have for
    1111
    2222
    3333
    4444
    5555
    6666
    7777
    to the actual combinations
    1 1 1 1
    2 1 1 0
    1 2 1 0
    1 1 2 0
    2 2 0 0
    1 3 0 0
    3 1 0 0
    I don't mind if my program has the zeros in it.
    Or am I going the completely wrong direction when it comes to this.

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,765
    Well the problem comes when you get to something like this
    1 1 2
    1 1 1 1

    Somehow, you need to output the common prefix to multiple permutations.

    If you can't store these in an array (how about a string - they're arrays, can you use them?), it's going to be harder to do.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Registered User
    Join Date
    Feb 2013
    Posts
    18
    Nope. We are learning Strings and Arrays right now, but for the purpose of this exercise, we are not allowed to use them. And that is what im having the main problem with. If I could use arrays I kinda (not a strong understanding of array and strings yet) see how the program would work. But I can't use them

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 02-09-2013, 02:43 AM
  2. Replies: 15
    Last Post: 12-13-2008, 09:32 AM
  3. New to programming, help with recursive functions.
    By HitchHiker in forum C Programming
    Replies: 6
    Last Post: 09-22-2008, 01:53 PM
  4. Windows programming for beginner (Absolute beginner)
    By WDT in forum Windows Programming
    Replies: 4
    Last Post: 01-06-2004, 11:21 AM
  5. need help with recursive functions
    By datainjector in forum C Programming
    Replies: 3
    Last Post: 07-18-2002, 08:32 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21