Efficenty: Recursion Assignment

f0ur

Newbie
Joined
Mar 6, 2019
Messages
25
Reaction score
11
For my Computer Science class my professor is trying to teach me and the rest of the class recursion via factorial.

The rules for factorial is as follows:

1) Problem must be naturally self reducing
2) Problem must have a "trivial case"

Pretty straight forward^^^

I found a solution to the problem, which was: take a long (2^32) and try to get an overflow

The code in question is:
Code:
#include <stdio.h>

int main()
{
  
   int testBase = 2; // Variable: the base for the exponent is 2
   int testExponent;
  
   // Note: 2^0 is our Trivial Case
  
   long testError = 1;
  
   int userInput;
  
   printf("[*] Input a number: ");
   scanf("%i", &userInput); // Note: starts acting 'weird' when 63 is inputted
  
   for( testExponent = userInput; testExponent != 0; --testExponent ) // While?
   {
      
       testError *= testBase;
      
       printf("[*] The number is: %li \n", testError);
      
   }
  
   printf("[COMPLETE] We are done! \n");
  
  
  
return 0;
}

It works, but I feel like it could be more efficient? I should mention that I am bad when it comes to C thinking... I also took the way to calculate the exponent from another source which I did put in the comment for the paper that the teacher is making us do. Maybe I am overthinking it or just not satisfied, but I want to be very good with C (like Linus good) since I know that if I know C very well, I can learn almost any other language.
 
Nice attempt. Your solution is iteration and not recursion.
 
How about (python 3):
Code:
def fact(z):
    return 1 if (z < 2) else z * fact(z-1)
 
print(fact(666))

It's recursive too.

Edit: More practical example

Code:
def fact(z):
    num = 1 if (z < 2) else z * fact(z-1)
    print("Next number is:" + str(num) + "\n")
    return num
 
number = input("Enter a number: \n")
fact(int(number))

The point I am trying to make is that the for loop could be avoided in your example.
 
Last edited:
This is a recursive solution in C. Note! This has no checks for invalid data.
Code:
#include <stdio.h>

int getPow(int number, int exp) {
  if (exp < 1) {
    return 1;
  }else {
    return number * getPow(number, exp - 1);
  }
}

int main (int argc, char ** argv) {
  fprintf(stdout, "%d\n", getPow(10, 2));
  fprintf(stdout, "%d\n", getPow(3, 10));
  fprintf(stdout, "%d\n", getPow(4, 1));
  fprintf(stdout, "%d\n", getPow(5, 0));
  return 0;
}
 
Back
Top